链表|24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
24.两两交换链表中的节点
自己审题思路
需要将后面的指针指向前面并移动至后两位，指针的起始位置选取比较重要
看完代码随想录题解后的收获
涉及到链表头结点操作的题目还是设置一个虚拟头结点方便一些
自己写的代码(错误)：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next ==nullptr) return head;
ListNode* pre = head;
ListNode* cur = head->next;
/* ListNode* dummy = new ListNode(0);
dummy->next = head; */
while(pre != nullptr|| cur != nullptr) {
ListNode* tmp = cur->next;
ListNode* tmp1 = cur->next->next;
cur->next = pre;
pre->next = tmp;
pre = tmp;
cur = tmp1;
}
return head->next;
}
};
上述代码有一个很严重的问题，就是两两反转中间的指针并没有改变：
以示例输入[1,2,3,4]为例，将2和1反转后->2指向1，将3和4反转后->4指向了3，但是1->3 而不是1->4，所以返回的链表是2->1->3.
代码(正确)：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next== nullptr) return head;
ListNode* dummy = new ListNode(0); // 设置一个虚拟头结点
dummy->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummy;
while (cur->next && cur->next->next) {
ListNode* tmp1 = cur->next; // 记录临时节点
ListNode* tmp2 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // dummy->2 || 1->4 关键，上述错误代码就是缺少这步操作！！！
cur->next->next = tmp1; // 2->1
cur->next->next->next = tmp2; // 1->3
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummy->next;
}
};
设置虚拟头结点后才方便完成所有交换操作
参考详解
19.删除链表的倒数第N个节点
自己审题思路
设法定位倒数第N个节点的前一个节点，然后完成删除操作
代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
ListNode* end = cur;
while(n--) {
end = end->next;
}
ListNode* tmp;
while (end) {
tmp = cur; // 保存要删除节点的前一个节点
cur = cur->next;
end = end->next;
}
tmp->next = cur->next;
return dummy->next;
}
};
看完代码随想录题解后的收获
其实思路是一致的
代码：
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; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete tmp;
return dummyHead->next;
}
};
参考详解
面试题 02.07. 链表相交
自己审题思路
求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
看完代码随想录题解后的收获
思路基本一致
代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
while(curA) {
curA = curA->next;
lenA++;
}
while(curB) {
curB = curB->next;
lenB++;
}
curA = headA;
curB = headB;
/* if (lenA > lenB) {
int i = lenA - lenB;
while (i--) {
curA = curA->next;
}
} else {
for(int j = 0; j < lenB - lenA; j++){
curB = curB->next;
}
} */
for (int i = 0; i < abs(lenA - lenB); i++) {
if (lenA > lenB) {
curA = curA->next;
} else {
curB = curB->next;
}
}
while (curA != curB) {
curA = curA->next;
curB = curB->next;
}
return curA;
}
};
参考详解
142.环形链表II
自己审题思路
知道使用快慢指针判断链表是否有环，但是入口怎么找没有思路
看完代码随想录题解后的收获
从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) return nullptr;
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (fast == slow) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1; // 返回环的入口
}
}
return nullptr;
}
};
链表示意图
slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，
n为fast指针在环内走了n圈才遇到slow指针，（y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
