24. 两两交换链表中的节点
文章链接：https://programmercarl.com/0024.两两交换链表中的节点.html#思路
视频讲解：https://www.bilibili.com/video/BV1YT411g7br
代码链接：https://leetcode.cn/problems/swap-nodes-in-pairs/
此题注意点：注意由于交换节点，head已经变换了位置，故最终不能直接返回head作为最终的答案，而应该返回dummyHead->next
此题思路：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead=new ListNode(0);
ListNode* cur=dummyHead;
dummyHead->next=head;
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;
}
ListNode* headp=dummyHead->next; //不能直接返回head，此时的head位置已经被改变
delete dummyHead;
return headp;
}
};
** 19.删除链表的倒数第N个节点
文章链接：https://programmercarl.com/0019.删除链表的倒数第N个节点.html#思路
视频链接：https://www.bilibili.com/video/BV1vW4y1U7Gf
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
这个题最开始我遍历了两边链表，题解如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* cur=dummyHead;
ListNode* cur1=dummyHead;
int size=0;
while(cur1->next!=nullptr){
size++;
cur1=cur1->next;
}
int x=size-n;
while(x--){
cur=cur->next;
}
ListNode* tmp=cur->next;
cur->next=cur->next->next;
delete tmp;
return dummyHead->next;
}
};
接下来尝试快慢指针：
思路：对于倒数第n步，如果让快指针先走n步，那么两个指针之间的步数差即为n
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* f=dummyHead;
ListNode* s=dummyHead;
//让f先走n步
while(n--){
f=f->next;
}
//接着两个一起走，直到f->next为空
while(f->next!=nullptr){ //注意这里如果写f!=nullptr就错了，因为我们要得到待删除节点的前一个位置的指针
f=f->next;
s=s->next;
}
ListNode* tmp=s->next;
s->next=s->next->next;
delete tmp;
return dummyHead->next;
}
};
面试题 02.07. 链表相交
文章链接：https://programmercarl.com/面试题02.07.链表相交.html
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
思路：
这个题返回的是两个链表后面相交的子链表（表示A，B两个链表最后所得的子链表长度一定相等），故一开始就要让链表长的指针后移，使得两个链表起始的时候指针后面的子链表长度相等。
易错：链表相交是指两个链表在某一个节点处 共享同一段内存位置，即从该节点开始，两个链表之后的节点完全相同（包括地址）。并不是根据节点的值判断，而是两个链表的节点对象需要实际重叠。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* a=headA;
ListNode* b=headB;
ListNode* curA=headA;
ListNode* curB=headB;
int sizeA=0;
int sizeB=0;
while(a!=nullptr){
sizeA++;
a=a->next;
}
while(b!=nullptr){
sizeB++;
b=b->next;
}
if(sizeA>sizeB){
int diff=sizeA-sizeB;
while(diff--){
curA=curA->next;
}
}
else if(sizeA<sizeB){
int diff=sizeB-sizeA;
while(diff--){
curB=curB->next;
}
}
while(curA!=nullptr){
if(curA==curB){ //注意不能写成curA->val==curB->val(内存位置也要一样)
return curA;
}
curA=curA->next;
curB=curB->next;
}
return NULL;
}
};
142.环形链表II
文章链接：https://programmercarl.com/0142.环形链表II.html#思路
视频讲解：https://www.bilibili.com/video/BV1if4y1d7ob
题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
简要思路：1.判断是否有环：相遇即有环（对于slow来说，fast是一个节点一个节点的靠近slow的）
2.有环找入口（详细见代码随想录）：相遇节点处，定义一个指针index1，在头结点处定一个指针index2；x=(n-1)C+z ===> x=(n-1)(x+y)+z
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* f=head;
ListNode* s=head;
//f != NULL 确保快指针当前节点不是空指针。
//f->next != NULL 确保快指针可以继续向前跳两步，防止越界访问 NULL 指针。
while(f!=NULL&&f->next!=NULL){
f=f->next->next;
s=s->next;
if(s==f){ //相遇就开始找环入口
ListNode* index1=f; //相遇点
ListNode* index2=head; //head头节点
while(index1!=index2){
index1=index1->next;
index2=index2->next;
}
return index1;
}
}
return NULL;
}
};