什么是線性表
n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列拾碌。
數(shù)據(jù)元素之間是一對一的關(guān)系。
線性表在數(shù)據(jù)結(jié)構(gòu)中的分類
1街望、順序表：邏輯結(jié)構(gòu)相鄰校翔，物理結(jié)構(gòu)相鄰。
典型代表：數(shù)組灾前。
2防症、鏈表：邏輯結(jié)構(gòu)相鄰，物理結(jié)構(gòu)不一定相鄰哎甲。
代表：數(shù)據(jù)結(jié)構(gòu)中的棧蔫敲、隊(duì)列
關(guān)于邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的介紹，可參考鏈接: https://www.cnblogs.com/tonglingliangyong/p/3944979.html
順序表與鏈表的一些屬性
順序表：
優(yōu)點(diǎn)是隨機(jī)存取表中的任意元素炭玫。
不足是做插入或刪除操作時(shí)奈嘿，需移動大量元素。
鏈表：
優(yōu)點(diǎn)是隨機(jī)插入或刪除時(shí)只需修改指針指向吞加，不需要移動元素裙犹。
不足是不能對元素進(jìn)行隨機(jī)存取。
順序表與鏈表的存在形式(以下C/C++形式呈現(xiàn))
數(shù)組： int array[] = {1, 2, 3, 4};
鏈表： struct ListNode {
int value;//數(shù)據(jù)域
ListNode* next;//指針域
};
應(yīng)用舉例(思路可參考文末)
一衔憨、數(shù)組
1.給定一個(gè)數(shù)組 {1, 2, 3, 4, 5}叶圃，將數(shù)組中的元素逆序
二、鏈表
1.給定一個(gè)數(shù)組nums和一個(gè)目標(biāo)值践图，
在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)掺冠，
并返回他們的數(shù)組下表。
eg：nums = [2, 7, 11, 15] target = 9
因?yàn)閚ums[0] + nums[1] = 2 + 7 = 9
所以平项，返回[0, 1]
2.給定一個(gè)鏈表：1->2->3->4->5赫舒，翻轉(zhuǎn)鏈表，
使得最后結(jié)果為：5->4->3->2->1
3.給定一個(gè)鏈表闽瓢，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)
eg： 1->2->3->4->5 n = 2
刪除倒數(shù)第二個(gè)節(jié)點(diǎn)后接癌，鏈表變?yōu)椋?1->2->3->5
思路：
一、數(shù)組
1.計(jì)算出數(shù)組a的長度：length
2.依次交換a[0] a[length - 1]
a[1] a[length - 2] 等的值(可利用異或特性)
二扣讼、鏈表
1.(1)兩層循環(huán)缺猛，遍歷數(shù)組，找出滿足條件的數(shù)據(jù)的下標(biāo)，
時(shí)間復(fù)雜度為o(n^2)
(2)利用map特性荔燎，遍歷一次數(shù)組耻姥，將數(shù)據(jù)作為key，
下標(biāo)index作為value有咨，添加到map中琐簇。再遍歷一次數(shù)組，
C++中座享，利用map.find(target - value)
來判斷是否有滿足條件的數(shù)據(jù)婉商，
時(shí)間復(fù)雜度為o(n) + o(n)，即為o(n)
2.利用4個(gè)指針渣叛，分別為pre丈秩、cur、next淳衙，
和tmp(暫存next指針的值)蘑秽，把原來next = cur->next，
修改為pre = cur->next
3.(1)遍歷獲取鏈表的長度箫攀，刪除倒數(shù)第n個(gè)節(jié)點(diǎn)肠牲，
也就是刪除正數(shù)第length - n + 1個(gè)節(jié)點(diǎn)
(2)用兩個(gè)指針來處理，first靴跛，second埂材，
先將first指針從列表的開頭向前移動 n+1步，
而第二個(gè)指針將從列表的開頭出發(fā)汤求，兩個(gè)指針被n個(gè)節(jié)點(diǎn)分開，
同時(shí)移動兩個(gè)指針保持恒定間隔严拒，
直到first指針到達(dá)最后一個(gè)結(jié)點(diǎn)扬绪，
此時(shí)第二個(gè)指針將指向從最后一個(gè)結(jié)點(diǎn)數(shù)起的第 n個(gè)結(jié)點(diǎn)。
重新鏈接第二個(gè)指針?biāo)玫慕Y(jié)點(diǎn)的 next 指針
指向該結(jié)點(diǎn)的下下個(gè)結(jié)點(diǎn)
核心代碼： while (first != NULL) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
