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

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

介绍

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

上述是自己看到这道题时写出的伪代码，可以看到两两进行交换的时候，需要改变的链条有三个（图中画黑圈的部分），因此，pre和p是主要的遍历指针。而t和q主要起到存放中间结点的作用，还没有看理解，不知道对不对QAQ。------------错了，当前指针即pre的位置弄错了。。。

首先要明确当前节点的位置，粉色代表当前节点，红色代表要交换的两个结点。

同样要定义虚拟头节点
dummyhead->next = head;
cur = dummyhead;   
while(cur->next!=NULL||cur->next->next!=NULL){ 
//遍历过程的终止条件要把握,分奇数和偶数//保存结点1 tmp = cur->next;//保存结点3tmp1 = cur->next->next->next;cur->next = cur->next->next; //结点2  cur->next--->2cur->next->next = tmp;//2--->1tmp->next = tmp1;//1--->3//移动current指针(结点不重要，一定要指向被交换的其前一个结点)cur = cur->next->next;
}
return dummyhead->next;

代码

/*** 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* 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;tmp->next = tmp1;cur = cur->next->next;}return dummyHead->next;}
};

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

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

介绍

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

题目的关键：找到倒数第n个结点，然后进行删除。

//如何找到倒数第n个结点 
//定义一个快指针，定义一个慢指针。然后让快指针先移动n步，然后快指针指向了空结点，此时慢指针指向了要删除的这个节点。 而操作结点应该指向要删除结点的前一个。即需要让慢指针指向要删除结点的前一个，为了达成这一目的，则需要让快指针多走一步，走n+1步。
//快指针多走一步后，快慢指针同时移动。fast = dummyHead
slow = dummyHead
//快指针先走n+1步
n++
while(n--&&fast!=NULL){fast = fast->NULL
}
//快慢指针同时移动
while(fast!=NULL){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;

代码

/*** 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* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;n++;while(n--&&fast!=nullptr){fast = fast->next;}while(fast!=nullptr){fast = fast->next;slow = slow->next;}ListNode* tmp = slow->next;slow->next = slow->next->next;delete tmp;return dummyHead->next;}
};

面试题 02.07. 链表相交

面试题 02.07. 链表相交

介绍

思路

该题是求两个链表交点结点的指针。

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

代码

相对于代码随想录中的代码，可能还是有点繁琐....
/*** 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;int len = 0;while(curA!=NULL){lenA++;curA = curA->next;}while(curB!=NULL){lenB++;curB = curB->next;}curA = headA;curB = headB;if(lenA>lenB){len = lenA-lenB;ListNode* curC = headA;while(len--){curC = curC->next;}while(curC!=NULL){if(curC== curB){return curC;}curC =curC->next;curB =curB->next;}return NULL;}else{len = lenB-lenA;ListNode* curC = headB;while(len--){curC = curC->next;}while(curC!=NULL){if(curC==curA){return curC;}curC =curC->next;curA =curA->next;}return NULL;}}
};

142.环形链表II

142.环形链表

介绍

思路

两问：判断链表是否有环/找到环的入口。

• 如何判断链表是否有环？——快慢指针

若链表无环，快指针以比较快的速度前进，慢指针以比较慢的速度前进，快慢指针在走的时候是无法相遇的；若链表有环，快慢指针则会相遇。

为什么快指针一定可以遇到慢指针？

可定义快指针每次走两个结点，慢指针每次走一个结点，在这种情况下快指针相对慢指针每次是走一个结点的，因此快指针绝对不会跳过慢指针。（快指针一个结点一个结点的去靠近慢指针）

• 如何找到环的入口？

假定快慢指针已在环内相遇，要找入口处的结点。

slow = x + y

fast = x + y + n(y+z) [n：快指针转的圈数 至少要走1圈 n>=1]

2slow = fast

x = n(y+z)-y

x = (n-1)(y+z)+z (n>=1)

若n=1，则有x=z

fast = head;
slow = head;
while(fast!=NULL&&fast->next!=NULL){fast = fast->next->next;slow = slow->next;if(fast == slow){index1 = fast/slow;index2 = head;while(index1!=index2){index1 = index1->next;index2 = index2->next;}return index1/index2;}
}
return NULL;

代码

/*** 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!=NULL&&fast->next!=NULL){fast = fast->next->next;slow = slow->next;if(fast == slow){ListNode* index1 =fast;ListNode* index2 = head;while(index1 != index2){index1 = index1->next;index2 = index2->next;}return index1;}}return NULL;}
};