链表操作 lc24 两两交换链表中的节点
这道题在熟悉链表操作后并不困难，在做的时候要想清楚每一步的顺序，可以画图辅助。
感觉步骤的顺序也可以更改，最重要的是不要出现空指针或丢失接下来数据位置
使用虚拟头节点可以一直找到头节点的位置
初见 pre+cur
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy_head = new ListNode(0,head);
ListNode* pre = dummy_head;
ListNode* cur = head;
while(pre && cur && cur->next){
pre->next = cur->next;
cur->next = pre->next->next;
pre->next->next = cur;
pre = cur;
cur = pre->next;
}
return dummy_head->next;
}
};
代码随想录答案24
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向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; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};
链表操作 lc19 删除链表倒数第N个节点
前面已经熟悉了删除链表节点的操作，但是刚看到这道题目还是感觉至少需要历遍两次，即第一次看一下链表长度，然后计算出删除节点的位置计数，再历遍一次找到目标节点并删除。
然而题目要求在一次遍历中完成。可以使用快慢指针（双指针）来解决。
即先让快指针与慢指针相距n个节点，再同时移动两个指针，当前面的快指针到尾后（NULL）的时候，后面的慢指针将正好指向想要删除的目标节点。在实际实现中，我们需要目标节点的前一个节点来进行删除操作，即我们需要落后于前面快指针n+1个节点的指针，指向目标的前一个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(0,head);
ListNode* fast = dummy_head;
ListNode* slow = dummy_head;
n++;
while(n--&&fast){
fast = fast->next;
}
while(fast){
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummy_head->next;
}
};
链表交点 lc面试题02.07.链表相交
这道题目的关键在于想到若两单向链表存在交点，则交点之后的所有节点都相同。所以可以找出较短的链表，并让较长链表从后往前保留较短链表相同长度，进行同时遍历。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
while(curA){
lenA++;
curA = curA->next;
}
while(curB){
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if (lenB>lenA){ //A永远长，curA指向长的链表头
swap(lenA,lenB);
swap(curA,curB);
}
//对齐
int diff = lenA - lenB;
while(diff--){
curA = curA->next;
}
while(lenB--){
if(curA==curB){
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
环形列表 lc142 环形列表II
本题编码并不是主要的难点，难点在于确定数学关系。
思路大致如下：
- 判断是否存在环
- 可以设立快慢指针，两个指针同时遍历，快指针每次走两步，慢指针每次走一步，如果存在环，两个指针会在环中相遇
- 因为两个指针相差为1，所以两个指针一定会相遇
- 接下来需要确定数学逻辑，考虑下图
慢指针路程：\(x+y\) （值得一提的是慢指针在相遇前走的路程不会超过一圈，可以这样想，慢指针走一圈，快指针可以走两圈，绝对会相遇）
快指针路程：\(x+n(y+z)+y\) （这里n是快指针所走圈数，快指针在相遇前一定会走一圈以上，即\(n\geq1\) 。因为快指针会比慢指针先进入环，然后再追上慢指针，这个过程至少经过环入口两次）
因为快指针速度是慢指针的2倍，所以慢指针所走路程的二倍是快指针的路程：
左右两边消掉一个\(x+y\)
\[x+y=n(y+z) \]把\(y\)放到右边
\[x=n(y+z)-y \]因为\(n\geq1\)继续推导
\[x=(n-1)(y+z)+y+z-y \]\[x=(n-1)(y+z)+z \]从这里我们不难看出，x和z的关系：我们让两个指针同时从head和相遇点开始遍历，head出发的指针走x个距离就可以到环入口，而相遇点出发的指针走z个距离后也会到环入口，根据上面公式，x与z的差除以环长度会整除（n=1时x=z），所以我们从相遇点出发的指针一定会与从head出发的指针相遇在环入口。
以上分析好后，代码并不难写。
/**
* 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) {
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast==slow){
ListNode *track1 = fast;
ListNode *track2 = head;
while(track1 != track2){
track1 = track1->next;
track2 = track2->next;
}
return track1;
}
}
return NULL;
}
};