题目：24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
本题目是一个模拟的过程，其过程如下图所示：
上面是一个模拟的过程，为了方便在代码的最前面加了一个虚拟头节点（dummyHead）。为了方便代码实现，也方便理解在代码中使用了4个指针变量分别用于对应在每次循环中所需要模拟的四个指针。
图中是[1,2,3,4]列表转换为[2,1,4,3]的过程，其步骤：
将各个节点的地址保存到对应的指针变量中
注意循环中断的条件
cur != nullptr &&cur->next != nullptr && cur->next->next != nullptr,是为了保证在每次循环的变量赋值的过程中不会发生nullptr->next的现象，就是防止一个空指针的下一个指针被用于赋值写循环过程：根据
cur->Node2->Node1->Node3的过程来进行每次的循环，并在循环结束后将当前指针cur向前挪动两个节点cur = cur->next->next返回值为dummyHead的下一个节点。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur != nullptr &&cur->next != nullptr && cur->next->next != nullptr)
{
ListNode* Node_1 = cur->next;
ListNode* Node_2 = cur->next->next;
ListNode* Node_3 = cur->next->next->next;
cur ->next = Node_2;
Node_2->next = Node_1;
Node_1->next = Node_3;
cur = cur->next->next;
}
return dummyHead->next;
}
};题目： 19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
该题最初的想法是使用双指针的方式，及通过双指针的方法来形成一个滑动区间，区间的长度即为倒数的个数-。
注意点：
需要找的节点是所需要删除节点的前一个节点，为了方便删除节点
滑动区间的长度为倒数第 n 个节点的n，
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* Node_Left = dummyHead;
ListNode* Node_Right = dummyHead;
while(n --){
Node_Right = Node_Right->next;
}
//要找到的是所需要删除的节点的前一个节点
while(Node_Right->next != nullptr){
Node_Left = Node_Left->next;
Node_Right = Node_Right->next;
}
Node_Left->next = Node_Left->next->next;
return dummyHead->next;
}
};题目：面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路：若是两个链表相交，则必有一段链表是重合的，然而给定的两个链表的长度是未知的，若是两个的长度相同，则从头开始逐一对比是可以的，若是不相同，则需要较长的链表将对比的初始节点后移，以实现对比链表从初始对比节点到末尾节点的长度相同，因此需要得到链表长度的差值。
/**
* 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) {
int A_size = 0;
ListNode* cur_A = headA;
//计算两个节点相差的长度
while(cur_A != NULL){
A_size ++;
cur_A = cur_A->next;
}
int B_size = 0;
ListNode* cur_B = headB;
while(cur_B != NULL){
B_size ++;
cur_B = cur_B->next;
}
int b = 0;
//再次初始化两个链表的节点位置
if(A_size > B_size){
cur_A = headA;
cur_B = headB;
b = A_size-B_size;
}else{
cur_A = headB;
cur_B = headA;
b = B_size-A_size;
}
while(b--){
cur_A = cur_A->next;
}
while(cur_A != NULL){
if(cur_A == cur_B){
return cur_A;
}
cur_A = cur_A->next;
cur_B = cur_B->next;
}
return NULL;
}
};题目：142.环形链表II
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
思路：就他呀的是到数学题，直接上方程做，这里的图片是代码随想录的图片（主要是自己画的太丑了），步骤：
设定快慢指针的速度，low速度为1，fast速度为2
计算相交前low和fast所经过的节点个数
low = x+y
fast = x+y+(y+z)*n，其中n为转的圈数
根据设定的速度可知，2low =fast因此2*(x+y)=x+y+(y+z)*n，所以x=(y+z)*n-y=(n-1)(y+z)+z，若此时n=1，则可以认为x = z。
根据x=z可以得出，从相遇节点和头节点以相同的速度出发到入口节点的距离是相同的。
其实无论n是多少对结果都不会有区别，因为(n-1)(y+z)是表示以相同的速度从头节点和相遇节点出发都将在入口节点相遇，只不过环内的指针可能多饶了(n-1)圈。
/**
* 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* low = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
low = low -> next;
if( fast == low){
break;
}
}
low = head;
while(fast != NULL && fast->next != NULL)
{
//注意这个判断一定要放在最前面，以防出现整个链表都是环的情况
if(low == fast){
return low;
}
fast = fast->next;
low = low->next;
}
return NULL;
}
};
评论