1.两两交换链表中的节点
引用:代码随想录 (programmercarl.com)
力扣题目链接
建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。
初始时,cur指向虚拟头结点,然后进行如下三步:
![24.两两交换链表中的节点1](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/24.%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%B91.png)
操作之后,链表如下:
![24.两两交换链表中的节点2](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/24.%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%B92.png)
看这个可能就更直观一些了:
![24.两两交换链表中的节点3](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/24.%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%B93.png)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while(cur->next != nullptr && cur->next->next != nullptr) { ListNode* tmp = cur->next; ListNode* tmp1 = cur->next->next->next;
cur->next = cur->next->next; cur->next->next = tmp; cur->next->next->next = tmp1;
cur = cur->next->next; } return dummyHead->next; } };
|
2.删除链表的倒数第N个节点
「思路:」先让快指针走 n+1步,之后让快慢指针同时走,直到快指针等于NULL,为什么是n+1呢,因为删除倒数第n一个节点需要前一个(即n-1)节点的信息,所以让快指针多走一步。
参考:代码随想录 (programmercarl.com)
- 定义fast指针和slow指针,初始值为虚拟头结点,如图:
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/19.%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.png)
- fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作),如图:
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/19.%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%B91.png)
- fast和slow同时移动,直到fast指向末尾,如题:
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/19.%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%B92.png)
- 删除slow指向的下一个节点,如图:
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/19.%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%B93.png)
此时不难写出如下C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != NULL) { fast = fast->next; } fast = fast->next; while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummyHead->next; } };
|
3.链表相交
面试题 02.07. 链表相交 - 力扣(LeetCode)
「重点:」这个题是指针相等,而不是值相等
「解决思路:」
- 遍历两个链表,计算长度,算出差值
- 让长的链表头指针先移动,对齐短的指针
![面试题02.07.链表相交_2](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4_2.png?imageSlim)
- 再依次遍历后面的指针,查到相等返回 curA,否则返回NULL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
|
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode * tmpA = headA; ListNode * tmpB = headB; int lenA = 0,lenB = 0;
while(tmpA != NULL) { lenA++; tmpA = tmpA -> next; }
while(tmpB != NULL) { lenB++; tmpB = tmpB -> next; } tmpA = headA; tmpB = headB;
if(lenB > lenA) { swap(lenB,lenA); swap(tmpB,tmpA); }
int charZhi = lenA - lenB;
while(charZhi--) { tmpA = tmpA -> next; }
while(tmpA != tmpB) { tmpA = tmpA -> next; tmpB = tmpB -> next; }
if(tmpA != NULL) { return tmpA; } else { return NULL; }
} };
|
4.环形链表II
力扣题目链接
4.1 解法1:存下走过的节点地址,进行对比查找
「思路:」遍历链表,存储每个节点的指针,先存储,再往下跳,之后再遍历数组是否存在此指针,存在说明找到了环的入口,返回当前节点。
「优缺点:」
- 优点:容易理解,思路简单暴力
- 缺点:时间复杂度偏高
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode * tmp = head; vector<ListNode *> arr; while(tmp != NULL) { arr.push_back(tmp); tmp = tmp -> next; if(find(arr.begin(),arr.end(),tmp) != arr.end()) { break; } } return tmp; } };
|
4.2 解法2:快慢双指针思路
「思路:」
参考:代码随想录 (programmercarl.com)
快指针fast一次走两步,慢指针slow一次走一步,显然如果有环,快指针一定会追上慢指针。
找到相遇点之后,要找到环的入口位置。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/20220925103433.png?imageSlim)
fast与slow相遇时,slow走过的步数 为 ==x + y== ,fast 走过的步数为 ==x + n(y + z)==
n表示转过的圈数。
因为 fast 走两步,slow走一步,时间一定时,慢指针要达到快指针的步数则需要变为两倍。
可得: ==2(x + y )=x+n(y+z)==
即而 推出: ==x = n(y+z) - y==
整理可得: ==x = (n-1)(y+z) +z==
因为 n圈数肯定大于等于1,可以想象在操场跑步的两人,快的人追慢的人,必然要跑完一圈,则 n >= 1
所以 当 n = 1时,推出 ==x = z==
即当找到相遇点后,让 fast(index1) 与 head(index2) 同时一步一步走,最终相遇的点就是入口。
![img](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II%EF%BC%88%E6%B1%82%E5%85%A5%E5%8F%A3%EF%BC%89-20231212161747071.gif)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode * fast = head; ListNode * slow = head;
while(fast != NULL and fast -> next != NULL) { slow = slow->next; fast= fast->next -> next; if(slow == fast) { ListNode * index1 = fast; ListNode * index2 = head;
while(index1 != index2) { index1 = index1 -> next; index2 = index2 -> next; }
return index1; } } return NULL; } };
|