概念
1.和數(shù)組一樣，鏈表也是一種線性表。
2.從內(nèi)存結(jié)構(gòu)來看队秩，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來昼浦，從而進行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)馍资。
3.鏈表中的每一個內(nèi)存塊被稱為節(jié)點Node。節(jié)點除了存儲數(shù)據(jù)外关噪，還需記錄鏈上下一個節(jié)點的地址鸟蟹，即后繼指針next乌妙。
注意：掌握好技巧，會提高正確率戏锹，真正理解后冠胯，舉一反三。將常見算法深刻理解之后锦针，大多數(shù)鏈表算法將不再是你的障礙荠察。
技巧
- 引用的理解
- 引用丟失和內(nèi)存泄漏
- 邊界判斷
- 利用哨兵(啞節(jié)點)
引用的理解
例如： a和b節(jié)點中插入x節(jié)點
x.next = a.next;
a.next = x;
//其中x.next引用存儲了a的下個節(jié)點next 的內(nèi)存地址
// a.next 引用儲存的是x節(jié)點的內(nèi)存地址
引用丟失和內(nèi)存泄漏
//上面是先將節(jié)點b 的內(nèi)存地址同時給多個引用，然后在改變a.next的引用
//如果我們先改變a.next的應(yīng)用
a.next = x;
x.next = a.next
//這樣會產(chǎn)生的現(xiàn)象是奈搜，a.next 指向了x的地址悉盆，但是b的地址就無法找到了。
//然后x.next = a.next; 這時a.next 已經(jīng)是x的地址了馋吗。相等于x.next = x焕盟，造成內(nèi)存泄漏。
image.png
邊界判斷
//1宏粤、鏈表為空
/**
* 尾插入元素是脚翘，如果頭節(jié)點為null，上面的代碼就不適用了绍哎，需要對節(jié)點做一個判斷
**/
if(a == null){
a = x;
}else{
Node temp = a;
while(temp.next != null){
temp = temp.next;
}
temp.next = x;
}
return a;
//刪除一個節(jié)點 a.next = a.next.next;但是如果刪除的是B節(jié)點来农，顯然也需要做判斷
//2、鏈表只有一個元素崇堰、兩個元素
//3沃于、頭節(jié)點和尾節(jié)點的處理
利用哨兵
// 上面在寫鏈表的處理的時候，插入新節(jié)點海诲，有兩種代碼邏輯繁莹，一種是頭節(jié)點null、一種是不為null特幔，邏輯是不一樣的
// 那么我們可以考慮另一種方式咨演，創(chuàng)建一個哨兵節(jié)點，這個節(jié)點什么元素都不存敬辣。只是簡化邊界判斷
Node temp;
Node head = new Node();
head.next = a;
temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = x;
return head.next;
//這樣的代碼就可以處理雪标，那兩種情況，同理刪除元素
常見算法
- 反轉(zhuǎn)鏈表
- 合并有序鏈表
- 刪除倒數(shù)第n個節(jié)點
- 鏈表中間節(jié)點
- 環(huán)狀鏈表檢測
反轉(zhuǎn)
// 輸入：1->2->3->4 輸出：4->3->2->1
// 思路： 1溉跃、迭代所有節(jié)點村刨，取當前節(jié)點 2、取當前節(jié)點的前一個節(jié)點 3撰茎、當前節(jié)點的next 指向前一個節(jié)點
// 實現(xiàn)：
Node reserver(Node curr) {
Node pre = null; //作為全局變量嵌牺，保證下次遍歷時能訪問到，初始值null，因為第一次遍歷頭節(jié)點的下個節(jié)點是null
while(curr != null){
//頭節(jié)點(1)的前一個節(jié)點是null:curr.next = null;
//但是下一個節(jié)點(2)的前一個節(jié)點是頭節(jié)點(1) curr.next =?逆粹，所以我們需要將前一個節(jié)點保存起來募疮，下次迭代還能訪問
curr.next = pre; // 當前節(jié)點curr的下個節(jié)點指向上一個 pre
pre = curr; //將當前節(jié)點給pre預(yù)存起來，保證當前處理不會改變僻弹，下次迭代時使用,
//如果沒有下次迭代阿浓，那么pre就是反轉(zhuǎn)后的頭節(jié)點
curr = curr.next;
}
return pre;
}
// 最后： 如果按照上面的代碼去執(zhí)行，會發(fā)現(xiàn)根本不是想要的結(jié)果蹋绽，1->null
// 原因： curr.next = pre 這行芭毙，curr的下個節(jié)點已經(jīng)被改變了(null),所以 curr = curr.next 其實等于curr = pre;
// 修改: 將curr原始下個節(jié)點預(yù)存，給一個變量 temp卸耘，然后curr = temp退敦；
Node reserver(Node node) {
Node pre = null; //作為全局變量，保證下次遍歷時能訪問到蚣抗，初始值null侈百，因為第一次遍歷頭節(jié)點的下個節(jié)點是null
while(node != null){
//頭節(jié)點(1)的前一個節(jié)點是null:curr.next = null;
//但是下一個節(jié)點(2)的前一個節(jié)點是頭節(jié)點(1) curr.next =?，所以我們需要將前一個節(jié)點保存起來翰铡，下次迭代還能訪問
Node temp = node.next;
node.next = pre; // 當前節(jié)點curr的下個節(jié)點指向上一個 pre
pre = node; //將當前節(jié)點給pre預(yù)存起來钝域，保證當前處理不會改變，下次迭代時使用
node = temp;
}
return pre;
}
排序
合并排序
//兩個有序鏈表合并一個有序鏈表
// 其中有一個為null,或者都為null
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode listNode = new ListNode(-1);
ListNode pre = listNode;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
pre.next = l1;
l1 = l1.next;
}else{
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
return listNode.next;
}
刪除倒數(shù)第n個節(jié)點
//統(tǒng)計鏈表長度
ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode first = head;
while (first != null) {
length++;
first = first.next;
}
//移除元素的前個節(jié)點的位置(length-=n)
//例如：1->2->3->4->5,5個元素移除倒數(shù)第2個節(jié)點(4)锭魔，也就是3=5-2是4的前節(jié)點网梢。只要將3 ->5 就完成了刪除。
length -= n;
//定義一個帶有頭節(jié)點的鏈表
ListNode dummy = new ListNode(0);
dummy.next = head;
first = dummy;
while (length > 0) {
length--;
first = first.next;
}
//如果length = 0赂毯，first = 3節(jié)點。所以將3.next = 3.next.next;
first.next = first.next.next;
return dummy.next;
}
//最后：邊界判斷 需要考慮拣宰，上面默認是參數(shù)是合法有效
//1党涕、鏈表為null,head=null,n=0 其中first.next =first.next.next 相當于 head = head.next，head=null巡社，所以會npt
//2、鏈表為一個元素/兩個元素
//3、頭/尾節(jié)點
//4虑润、n值非法的情況
鏈表的中間節(jié)點
// 聽到中間立馬想到弥臼，快慢指針
public ListNode middleNode(ListNode head) {
ListNode p = head; ListNode q = head;
while(q!=null && q.next!=null){
p = p.next;
q = p.next.next;
}
return p;
}
鏈表中環(huán)檢測
public static boolean hasCycle(ListNode head) {
// 如果2個節(jié)點以上，有循環(huán)鏈表朝群，現(xiàn)象：迭代一直會走下去燕耿。如何判斷有循環(huán)，第一個想法某個節(jié)點迭代了兩次姜胖。
// 1->2->3->4 4又指向了1 環(huán)就形成了誉帅，如果依次迭代，將之前元素放入集合，如果集合中存在蚜锨，則又環(huán)
Set<ListNode> listNodes = new HashSet<>();
while (head!=null){
if (listNodes.contains(head)){
return true;
}
listNodes.add(head);
head = head.next;
}
return false;
}
//第二種 方式档插，就是使用快慢指針，想一下亚再，如果存在環(huán)的話郭膛。走的快的人肯定會跟走的慢的相遇，
//想一下操場上氛悬，有一個人速度是你的兩倍则剃，如果你跑完一圈，那個人肯定會跟你相遇圆雁。
//如果你跑到終點了忍级，還沒和你沒有相遇說明人家早到終點，停下來了伪朽。
public static boolean hasCycle(ListNode head) {
// 判斷邊界 轴咱，1、head = null 2烈涮、head.next = null 3朴肺、head.next.next =null 4、頭尾節(jié)點坚洽。
// 如果null 或者只有一個節(jié)點是不能形成循環(huán)節(jié)點(本身指向本身節(jié)點除外)
if(head == null || head != null){
return false;
}
// 是否是統(tǒng)一起點沒有關(guān)系戈稿，如果是環(huán)肯定會相遇
ListNode p = head; ListNode q = head.next;
while(q != null && q.next != null){
if(p == q){
return true;
}
p = p.next;
q = q.next.next;
}
return false;
}
