LeetCode 24.两两交换链表中的节点
题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
方法：
本题先加入一个虚拟头节点，这样能更方便地在最后返回头节点。然后按照题目要求改变指针的指向，例如原来是虚拟头节点->节点1->节点2->节点3，通过指针操作将顺序改为虚拟头节点->节点2->节点1->节点3，这样就能够实现节点的交换。
思路：
当链表节点数为奇数时，循环终止的条件是cur->next为空，当链表节点数为偶数时，循环终止的条件是cur->next->next为空。也可以换个角度想，因为在操作指针指向的时候，cur->next、cur->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* swapPairs(ListNode* head) {
ListNode* vhead=new ListNode(0);
vhead->next=head;
ListNode* cur=vhead;
while(cur->next!=NULL&&cur->next->next!=NULL)
{
ListNode* temp=cur->next;
ListNode* p=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=temp;
cur->next->next->next=p;
cur=cur->next->next;
}
return vhead->next;
}
};
LeetCode 19.删除链表的倒数第N个节点
题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路:
这道题的难点是找到倒数第n个节点，这里采用双指针的方法，定义一组指针front、last，让front先走n+1步，然后两个指针再同时向前移动，直到front为空，此时last指向的是倒数n个节点的前一个节点，再进行删除操作就行了。
注意：
1、这里是先走了n+1步，因为删除节点要找到前一个节点才行；
2、让front先走n+1步的操作中，因为n的数值可能会大于整个链表的长度，所以需要要添加front！=NULL的限制条件；
3、因为要走n+1步，如果先走了n步再在循环外走一步的话，front可能产生对空指针进行操作，所以进入循环前对n++。
代码：
/**
* 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* vhead=new ListNode(0);
vhead->next=head;
ListNode* front=vhead;
ListNode* last=vhead;
n++;
while(n--&&front!=NULL)
{
front=front->next;
}
while(front!=NULL)
{
last=last->next;
front=front->next;
}
ListNode* temp=last->next;
last->next=last->next->next;
delete temp;
return vhead->next;
}
};
LeetCode 面试题 02.07.链表相交
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路：
这道题考察的是链表相交。链表相交不是指节点的元素值相同，而是指由题目指定的节点开始，在某一个节点处两个链表的指针开始相等，后续节点的指针也是相等的，但是这些节点的数值可以相等也可以不等，而这道题也就是让我们找到题目指定的那个节点的位置，这一点可以联系官方给的示例1来理解。
我们的目的是找到那个节点的位置，因为在相交之后，两个链表的后续节点地址都是一致的，所以相当于把两个链表的尾端对齐，然后找第一个相同的地址的节点位置，地址的比较通过两个链表各自的指针移动、对比进行。假设A链表的长度大于B链表，A、B链表尾端对齐，因为一旦相交，A、B链表的地址是一致的，不存在A链表还继续，B链表就结束的情况，所以A链表大于B链表的那一部分就可以不用比较。之后就把A链表的指针移到与B链表长度相等的地方，判断A链表指针是否与B链表指针相同，相同则返回A链表指针，循环结束还不同就返回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) {
ListNode* Acur=headA;
ListNode* Bcur=headB;
int Alen=0;
int Blen=0;
while(Acur!=NULL)
{
Alen++;
Acur=Acur->next;
}
while(Bcur!=NULL)
{
Blen++;
Bcur=Bcur->next;
}
Acur=headA;
Bcur=headB;
if(Blen>Alen)
{
swap(Alen,Blen);
swap(Acur,Bcur);
}
int gap=Alen-Blen;
while(gap--)
{
Acur=Acur->next;
}
while(Acur!=NULL)
{
if(Acur==Bcur)
{
return Acur;
}
Acur=Acur->next;
Bcur=Bcur->next;
}
return NULL;
}
};
LeetCode 142.环形链表Ⅱ
题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回NULL。
思路：
这道题采用的是双链表的解法，一个快指针fast，每次走两个节点，一个慢指针，每次走一个节点，当两个指针相遇的时候，说明链表里面有环。假设环的入口地址是第x个节点，两个指针在环内相遇，相遇点距离x节点为y，环的剩余距离为z，因为两个指针在相同时间内相遇，所以有x+y=2（x+y）+y+n（z+y），其中n表示快指针在环内转的圈数，整理后得到x=n（z+y）-y，也即x=（n-1）（z+y）+z；也就是说假设此时有两个指针index1、index2。index1从head出发，index2从相遇点出发，它们的速度都是每次一个节点，那么它们一定会在环的入口地址处相遇，index1就是环的入口地址。
代码：
/**
* 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* p=fast;
ListNode* q=head;
while(p!=q)
{
p=p->next;
q=q->next;
}
return q;
}
}
return NULL;
}
};
