Leetcode日記：19&24&84.鏈表相關(guān)操作
19.刪除倒數(shù)第N個(gè)元素
19-題目
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
19-題目分析
首先颖系，題目要求刪除鏈表中倒數(shù)第n個(gè)元素。
其實(shí)很簡(jiǎn)單，我們只需要遍歷一遍鏈表逗抑，知道鏈表的元素個(gè)數(shù)诱建。再次遍歷钮蛛，找到length-n個(gè)元素就可以了。
但是題目有進(jìn)階要求受神，能不能只遍歷一次抛猖？
答案是肯定的。請(qǐng)看下面代碼：
19-代碼
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0);
ListNode slow = start, fast = start;
slow.next = head;
//Move fast in front so that the gap between slow and fast becomes n
for(int i=1; i<=n+1; i++) {
fast = fast.next;
}
//Move fast to the end, maintaining the gap
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
//Skip the desired node
slow.next = slow.next.next;
return start.next;
}
19-代碼分析
這里用到了一個(gè)很巧妙的方法鼻听，我將它命名為“雙指針?lè)蛛x法”财著，主要思想就是先讓這兩個(gè)指針岔開(kāi)n個(gè)元素，然后兩個(gè)指針同時(shí)向前步進(jìn)撑碴。當(dāng)前面的元素到最后時(shí)撑教，后面那個(gè)元素剛好指向倒數(shù)第n個(gè)元素。
算法示意圖：
24.成對(duì)交換節(jié)點(diǎn)
24-題目
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
24-題目分析
結(jié)點(diǎn)交換醉拓，是鏈表中老生常談的一個(gè)話題伟姐，看似簡(jiǎn)單，編寫(xiě)程序的時(shí)候亿卤，容易被節(jié)點(diǎn)繞暈愤兵，那么我們就看看這個(gè)程序時(shí)如何編寫(xiě)的吧！
24-代碼
public ListNode swapPairs(ListNode head) {
if ((head == null)||(head.next == null))
return head;
ListNode n = head.next;
head.next = swapPairs(head.next.next);
n.next = head;
return n;
}
24-代碼分析
這里采用了遞歸排吴，是因?yàn)槿绻麖那巴蠼粨Q的話秆乳，前面一對(duì)鏈接的一定要是已經(jīng)交換好的下一對(duì)，所以程序的運(yùn)行順序是先將最后的交換好傍念，然后逐漸往回過(guò)渡矫夷。
如圖所示，每一層遞歸憋槐，我們都會(huì)創(chuàng)建new一個(gè)新節(jié)點(diǎn)双藕，這個(gè)節(jié)點(diǎn)首先保存為head.next的信息，然后進(jìn)行遞歸阳仔，遞歸返回輸入鏈表的交換后的頭節(jié)點(diǎn)忧陪，隨后將返回的頭節(jié)點(diǎn)設(shè)置為head.next扣泊。最后，將n.next指向head完成交換嘶摊，此時(shí)原來(lái)的head.next完全被隔離延蟹，被系統(tǒng)回收。
這道題看似容易叶堆，實(shí)際上還是需要一番思考的阱飘。
82.刪除鏈表重復(fù)元素II
82-題目
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
82-題目分析
之前有一道題是保留一個(gè)重復(fù)元素，刪除多余的虱颗，那道題比較簡(jiǎn)單沥匈，這道題的意圖是：只要是重復(fù)的元素，都刪除忘渔，一個(gè)不留高帖。
這就牽扯到，你要有兩個(gè)指針畦粮，一個(gè)指針用于記錄上一個(gè)不重復(fù)元素散址，另一個(gè)指針負(fù)責(zé)向前步進(jìn)檢測(cè)并刪除重復(fù)元素。
82-代碼
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return null;
ListNode FakeHead=new ListNode(0);
FakeHead.next=head;
ListNode pre=FakeHead;
ListNode cur=head;
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
if(pre.next==cur){
pre=pre.next;
}
else{
pre.next=cur.next;
}
cur=cur.next;
}
return FakeHead.next;
}
82-代碼分析
從代碼中我們可以看出宣赔，代碼用了兩個(gè)指針预麸，第一個(gè)指針pre用來(lái)記錄最后一個(gè)不重復(fù)的指針（這個(gè)指針一定不會(huì)被刪除掉）。第二個(gè)指針cur用來(lái)記錄當(dāng)前位置拉背，用它來(lái)判斷是否該元素為重復(fù)元素(cur.next!=null&&cur.val==cur.next.val)师崎，利用一個(gè)循環(huán)，直接找到下一個(gè)出現(xiàn)的不重復(fù)元素椅棺，這里有兩種情況犁罩，一種是循環(huán)沒(méi)有被執(zhí)行（即cur為一個(gè)不重復(fù)元素），那么cur沒(méi)有移動(dòng)两疚，我們讓pre=pre.next床估，來(lái)更新最后一個(gè)不重復(fù)元素。如果是重復(fù)元素诱渤，則跨過(guò)cur丐巫，執(zhí)行pre.next=cur.next。
鏈表問(wèn)題總結(jié)
鏈表問(wèn)題在所有數(shù)據(jù)結(jié)構(gòu)里面所示較為簡(jiǎn)單的一種勺美。而且相對(duì)來(lái)說(shuō)問(wèn)題的變數(shù)比較少递胧，我們著重關(guān)注以下幾個(gè)問(wèn)題
-
dummy啞節(jié)點(diǎn)
我們可以看到，上面題目中赡茸，第一題的
ListNode start = new ListNode(0);
最后一道題的
ListNode FakeHead=new ListNode(0);
都首先創(chuàng)建了一個(gè)新節(jié)點(diǎn)缎脾，這個(gè)結(jié)點(diǎn)的下一個(gè)往往是輸入的頭節(jié)點(diǎn)，為什么會(huì)這么設(shè)置呢占卧？
啞節(jié)點(diǎn)設(shè)置的主要原因：
避免頭節(jié)點(diǎn)可能由于某種原因被刪除等一系列問(wèn)題而導(dǎo)致的邊界問(wèn)題遗菠，簡(jiǎn)化代碼联喘。 -
雙指針設(shè)計(jì)
鏈表的很多問(wèn)題用雙指針都會(huì)降低一些時(shí)間復(fù)雜度。比如leetcode24等很多問(wèn)題可以應(yīng)用在很多場(chǎng)景中：
- 刪除鏈表中元素
- 拆分鏈表
- 找出中點(diǎn)或中位數(shù)
- 尋找鏈表是否存在環(huán)
- 尋找范圍
還有更多應(yīng)用辙纬，但是思想都是不變的豁遭，指針一快一慢，具體快多少贺拣，看題目中具體要求蓖谢。這便是著名的“快慢指針”
更多關(guān)于鏈表的問(wèn)題
更多關(guān)于回溯算法的問(wèn)題請(qǐng)轉(zhuǎn)到鏈表標(biāo)簽
