代码随想录day4 ● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

24. 两两交换链表中的节点

 1 class Solution {
 2 public:
 3     ListNode* swapPairs(ListNode* head) {
 4         //创建虚拟头结点
 5         ListNode* dummyHead = new ListNode(0);
 6         //将虚拟头结点接在头结点后面
 7         dummyHead->next = head;
 8         //创建cur结点用于遍历
 9         ListNode* cur = dummyHead;
10         //持续向后查找
11         while (cur->next != nullptr && cur->next->next != nullptr){
12             //创建tmp，太tmp1用于保存结点
13             ListNode* tmp = cur->next;
14             ListNode* tmp1 = cur->next->next;
15 
16             //步骤1
17             cur->next = cur->next->next;
18             //步骤2
19             cur->next->next = tmp;
20             //步骤3
21             cur->next->next->next = tmp1;
22 
23             cur = cur->next->next;    
24         }
25         return dummyHead->next;  
26     }
27 };

19. 删除链表的倒数第 N 个结点

笨蛋解法：

第一步：先统计链表节点个数

第二步：查找到第（size - n）个结点

第三步：删除操作

 1 class Solution {
 2 public:
 3     ListNode* removeNthFromEnd(ListNode* head, int n) {
 4         ListNode* _dummyhead = new ListNode(0);
 5         _dummyhead->next = head;
 6         ListNode* cur = _dummyhead;
 7         int _size = 0;
 8         //遍历链表，统计节点个数
 9         while (cur->next != nullptr){
10             cur = cur->next;
11             _size++;
12         }
13         //查找倒数第n个结点，即第m = （_size - n）
14         cur = _dummyhead;
15         int m = _size - n;
16         while (m--){
17             cur = cur->next;
18         }
19         //删除操作
20         ListNode* tmp = cur->next;
21         cur->next = cur->next->next;
22         delete tmp;
23         //返回头结点
24         return _dummyhead->next;
25 
26     }
27 };

双指针解法：

自己写的双指针解法：

 1 class Solution {
 2 public:
 3     ListNode* removeNthFromEnd(ListNode* head, int n) {
 4         //创建虚拟头结点
 5         ListNode* _dummyHead = new ListNode(0);
 6         _dummyHead->next = head;
 7         //创建快慢指针
 8         ListNode* slow = _dummyHead;
 9         ListNode* fast = _dummyHead;
10         //快指针向后查找n步
11         while (n--){
12             fast = fast->next;
13         }
14         //fast->next != nullptr 快慢指针持续向后查找
15         while (fast->next != nullptr){
16             fast = fast->next;
17             slow = slow->next;
18         }
19         //创建临时指针用于删除
20         ListNode* tmp = slow->next;
21         slow->next = slow->next->next;
22         delete tmp;
23         //返回链表头结点
24         return _dummyHead->next;
25     }
26 };

卡哥双指针解法：

 1 class Solution {
 2 public:
 3     ListNode* removeNthFromEnd(ListNode* head, int n) {
 4         //创建虚拟头结点
 5         ListNode* dummyHead = new ListNode(0);
 6         dummyHead->next = head;
 7         //创建快慢指针
 8         ListNode* slow = dummyHead;
 9         ListNode* fast = dummyHead;
10         //fast指针向后移动n步，此时fast指针和slow指针相隔n步
11         while(n-- && fast != NULL) {
12             fast = fast->next;
13         }
14         // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
15         fast = fast->next; 
16         while (fast != NULL) {
17             fast = fast->next;
18             slow = slow->next;
19         }
20         //删除结点
21         slow->next = slow->next->next;
22         //返回头结点
23         return dummyHead->next;
24     }
25 };

面试题 02.07. 链表相交

第一步：分别计算链表的长度；

第二步：使得链表A为长度较长的链表；

第三步：链表A先向后查找gap步；

第四步：链表A和链表B同时向后查找；

第五步：返回相交的结点。

 1 class Solution {
 2 public:
 3     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
 4         //创建查询所需指针
 5         ListNode* curA = headA;
 6         ListNode* curB = headB;
 7         //分别计算两个链表长度
 8         int lenA = 0, lenB = 0;
 9         while (curA != nullptr){
10             lenA++;
11             curA = curA->next;
12         }
13         while (curB != nullptr){
14             lenB++;
15             curB = curB->next;
16         }
17         //重置查找所用的头结点
18         curA = headA;
19         curB = headB;
20         //让链表A为最长的链表
21         if (lenB > lenA){
22             swap(curA, curB);
23             swap(lenA, lenB);
24         }
25         //计算curA和curB的长度差
26         int gap = lenA - lenB;
27         //使得curA和curB处于相同起点
28         while (gap--){
29             curA = curA->next;
30         }
31         //开始遍历
32         while(curA != nullptr){
33             if (curA == curB){
34                 return curA;
35             }
36             curA = curA->next;
37             curB = curB->next;
38         }
39         return nullptr;
40         
41     }
42 };

142. 环形链表 II

快慢指针法：

定义两个指针从头开始遍历，若存在环，则两个指针必定会在环中相遇。

从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

 代码如下：

 1 class Solution {
 2 public:
 3     ListNode *detectCycle(ListNode *head) {
 4         //创建快慢指针
 5         ListNode* fast = head;
 6         ListNode* slow = head;
 7         //快慢指针开始遍历链表
 8         while(fast != nullptr && fast->next != nullptr) {
 9             slow = slow->next;
10             fast = fast->next->next;
11             // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
12             if (slow == fast) {
13                 //创建index1和index2用于查找链表环的入口
14                 ListNode* index1 = fast;
15                 ListNode* index2 = head;
16                 while (index1 != index2) {
17                     index1 = index1->next;
18                     index2 = index2->next;
19                 }
20                 //返回入口结点
21                 return index2; // 返回环的入口
22             }
23         }
24         return nullptr;
25     }
26 };