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

24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：

1. 设置一个虚拟头结点，设置一个当前结点等于虚拟头结点，进行移动操作。指向两两交换的第二个结点，第二结点的next指针指向原本的第一个结点
2. 在移动之前将第一个结点和第三个结点存储起来，防止结点丢失
3. 虚拟结点向后移动两位，进行第二轮的两两交换
4. 用虚拟头结点得到重置后的头结点。

/**
 * 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* dummynode=new ListNode(0);//设置虚拟头结点
        dummynode->next=head;
        ListNode* cur = dummynode;//设置当前执行结点
        while(cur->next!=nullptr&&cur->next->next!=nullptr)
        {
            ListNode* temp1 = cur->next;//temp1储存原链表的第一个结点
            ListNode* temp2 = cur->next->next->next;//temp2储存原链表的第二个结点
            cur->next=cur->next->next;//将第二个结点变成第一个结点
            cur->next->next=temp1;//将第二个节点连接原链表的第一个结点
            cur->next->next->next=temp2;//把第三个结点连接起来
            cur=cur->next->next;//移动当前结点
        }
        ListNode* newhead=dummynode->next;
        delete dummynode;
        return newhead;
    }
};

删除链表的倒数第n个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：

1. 设置两个指针，一个快指针，一个慢指针，快指针先移动n步，再移动1步（确保慢指针能移动到目标结点的上一个，方便进行删除操作）
2. 同时移动快慢指针，直到快指针指向空
3. 慢指针对结点进行删除操作

/**
 * 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* dummynode=new ListNode(0);
        dummynode->next=head;
        ListNode* fast=dummynode;//设置快指针
        ListNode* slow=dummynode;//设置慢指针
        while(n--&&fast!=NULL)//快指针先移动n步
        {
            fast=fast->next;
        }
        fast=fast->next;//多移动一步，方便慢指针进行移除操作
        while(fast!=NULL)
        {
            fast=fast->next;
            slow=slow->next;
        }
        ListNode* temp=slow->next;
        slow->next=slow->next->next;
        delete temp;

        head=dummynode->next;
        delete dummynode;
        return head;
    }
};

02.07.链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

思路：

1. 求链表的交点就是求链表指针相同，首先求出两个链表的长度
2. 求出链表A和链表B的差值s
3. 将长的那条链表的头结点移动s个位置
4. 同时移动链表A和链表B的指针，直到两个指针相等，相等的指针就是两个链表的交点
5. 为了保证移动便利，始终坚持A链表是最长的那个链表，使用C++的标准库函数swap()实现两个链表值的交换。

/**
 * 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!=NULL)//判断其是否为空指针
        {
            lenA++;
            curA=curA->next;
        }
        while(curB!=NULL)
        {
            lenB++;
            curB=curB->next;
        }
        curA=headA;//前面对指针进行了移动的操作，所以要重新返回头结点
        curB=headB;
        if(lenA<lenB)
        {
            swap(curA,curB);//swap交换变量的值
            swap(lenA,lenB);
        }
        int s = lenA-lenB;//求出两条链表的差值
        while(s--)
        {
            curA=curA->next;
        }
        while(curA!=NULL)
        {
            if(curA==curB)
            {
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return NULL;
    }
};

142.环形链表

142. 环形链表 II - 力扣（LeetCode）
思路：
解决这个问题首先要考虑两种情况

• 链表是否有环
• 链表如果有环，那么环的入口在哪里

链表是否有环
要判断链表是否有环:

1. 设定两个指针，快指针移动两步，慢指针移动一步
2. 入环后两个指针就在环内移动
3. 如果链表有环，那么两个指针一定会相遇
4. 两个指针在链表中相遇证明链表有环，没有相遇，证明链表无环。

环的入口问题
这是一个数学问题：
设头结点到入口的距离为x,r入口到相遇点的距离为y,相遇点到入口的距离为z.
那么慢指针到相遇点的走过的结点数就是x+y;
快指针走过的节点数就是x+y+n(y+z);
由于快指针走过的结点数是慢指针的两倍，所以他们相遇时2（x+y）=x+y+n(y+z)；
两边同时消掉一个x+y；
得到x+y=n(y+z)；
作一个变形的x=(n-1)(y+z)+z；
当快指针走了第一圈时，快慢指针就能相遇，故n=1时，x=z;

此时，从相遇点头结点同时开始移动指针，当指针相遇时，就是环形链表的入口。

/**
 * 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)
        {
            slow=slow->next;//慢指针移动一步
            fast=fast->next->next;//快指针移动两步
            if(fast==slow)//找到环形链表的相遇点
            {
                ListNode* index1=fast;
                ListNode* index2=head;
                while(index1!=index2)//从相遇点和头结点开始移动，直到两个指针相等
                {
                    index1=index1->next;
                    index2=index2->next;
                }
                return index2;
            }
        }
        return NULL;
    }
};