DAY4 鏈表part02

今日任務

● 24. 兩兩交換鏈表中的節點

● 19.刪除鏈表的倒數第N個節點

● 面試題 02.07. 鏈表相交

● 142.環形鏈表II

● 總結 //有一定難度，需要好好琢磨

24. 兩兩交換鏈表中的節點

用虛擬頭結點，這樣會方便很多。

題目鏈接/文章講解/視頻講解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

*注意畫圖理清思路

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* swapPairs(ListNode* head) {
14         ListNode* dummy=new ListNode(0);
15         dummy->next=head;
16         ListNode* p=dummy;
17         ListNode* q=dummy->next;
18 
19         while(q!=NULL&&q->next!=NULL)
20         {
21             ListNode* tmp=q->next;
22             q->next=tmp->next;
23             tmp->next=q;
24             p->next=tmp;
25 
26             p=p->next->next;//p走兩格
27             q=q->next;
28         }
29         head=dummy->next;
30         return head;
31     }
32 };

19.刪除鏈表的倒數第N個節點

雙指針的操作，要注意，刪除第N個節點，那么我們當前遍歷的指針一定要指向第N個節點的前一個節點

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

*雙指針的經典用法：讓fast先走N，再讓fast和slow同時走，直到fast到尾結點，此時slow指向目標節點的前一位置，即倒數N+1結點；

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* removeNthFromEnd(ListNode* head, int n) {
14         ListNode* dummy=new ListNode(0);
15         dummy->next=head;
16         ListNode* fast=dummy;
17         ListNode* slow=dummy;
18         for(int i=0;i<n;i++) fast=fast->next;
19 
20         while(fast->next!=NULL)//注意此條件
21         {
22             fast=fast->next;
23             slow=slow->next;
24         }//出循環時fast指向最后一個節點，slow指向目標節點前一個結點
25         ListNode* tmp=slow->next;
26         slow->next=tmp->next;
27         delete(tmp);
28         //以上三行可寫作 slow->next=slow->next->next;
29 
30         head=dummy->next;
31         return head;
32     }
33 };

面試題 02.07. 鏈表相交

題目鏈接/文章講解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

方法一：讓A和B“對齊”，從而同步移動指針，可以找到公共首節點；

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9  //對齊
10 class Solution {
11 public:
12     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
13         int lenA=0;
14         int lenB=0;
15         ListNode* cura=headA;
16         ListNode* curb=headB;
17         while(cura!=NULL) 
18         {
19             lenA++;
20             cura=cura->next;
21         }
22         while(curb!=NULL) 
23         {
24             lenB++;
25             curb=curb->next;
26         }
27         cura=headA;
28         curb=headB;
29         if(lenA>lenB)
30         {
31             int cnt=lenA-lenB;
32             while(cnt--) cura=cura->next;
33         }
34         else if(lenA<lenB)
35         {
36             int cnt=lenB-lenA;
37             while(cnt--) curb=curb->next;
38         }//分類討論
39         while(cura!=NULL&curb!=NULL)
40         {
41             if(cura==curb) return cura;
42             else 
43             {
44                 cura=cura->next;
45                 curb=curb->next;
46             }
47         }
48         return cura;
49         }
50 };

方法二：合并鏈表實現同步移動（畫圖）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9  //合并鏈表實現同步移動
10 class Solution {
11 public:
12     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
13         ListNode* curA=headA;
14         ListNode* curB=headB;
15         while(curA!=curB)
16         {
17             if( curA==NULL) curA=headB;
18             else curA=curA->next;
19 
20             if(curB==NULL) curB=headA;
21             else curB=curB->next;
22         }
23         return curA;
24     }//理解
25 };

142.環形鏈表II

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

*明確任務：判斷有無環和找到入環的第一結點

*思想：雙指針判斷有無環（fast=fast->next->next,slow=slow->next),經證明，若fast和slow相遇，則一定有環且在環內相遇；

　　　數學證明，若meet從相遇結點出發，index從head出發，則二者會在環的首節點相遇（相同速度）；

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *detectCycle(ListNode *head) {
12         ListNode *fast=head;
13         ListNode *slow=head;
14 
15         while(fast!=NULL&&fast->next!=NULL)//判斷有沒有環
16         {
17             slow=slow->next;
18             fast=fast->next->next;
19             if(fast==slow)//有環
20             {
21                 ListNode* meet=slow;//相遇節點
22                 ListNode* index=head;//首節點
23 
24                 while(meet!=index)
25                 {
26                     meet=meet->next;
27                     index=index->next;
28                 }相遇則找到環的入口
29                 return meet;
30             }
31         }
32         
33             return NULL;//沒找到
34     }
35 };

總結

https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E6%80%BB%E7%BB%93%E7%AF%87.html

重點：虛擬結點的使用非常重要~

posted @ 2024-07-20 22:41 xzdmzrc 閱讀(14) 評論(0) 收藏舉報

刷新頁面返回頂部

xzdmzrc221202