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

题目链接：24. 两两交换链表中的节点

【思路】

画图后就容易理解了，别忘了定义临时变量保存要被丢掉的节点。借用卡哥的图来看一下：
来自代码随想录
注意：

设置虚拟头结点可以方便的操作头结点
注意设置临时变量保存要断开的节点
画图！画图！画图！不画图很容易乱。

【代码】

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); //虚拟头节点
        dummyHead->next = head;
        ListNode* cur=dummyHead;
        while(cur->next && cur->next->next) { //判断顺序不能混，一定cur->next不为空时，cur->next->next 才有意义
            ListNode* temp = cur->next;
            ListNode* temp1 = cur->next->next->next;
            cur->next = cur->next->next; //步骤一
            cur->next->next =temp; //步骤二
            temp->next = temp1; //步骤三
            cur = cur->next->next;
        }
        return dummyHead->next;
    }
};

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

题目链接： 19.删除链表的倒数第N个节点

【思路】

采用双指针进行操作，首先快指针先走n个节点，然后快慢指针同时前进，当快指针到达链表尾节点，即fast->next = Null，慢指针就指向了要删除的上一个节点

-我们要删除节点，需要知道它的上一个节点，才能操作

【代码】

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        ListNode* pre = dummyHead;
        while (n--) {
            cur = cur->next;
        }
        while (cur->next != nullptr) {
            pre = pre->next;
            cur = cur->next;
        }
        ListNode* temp = pre->next;
        pre->next = pre->next->next;
        delete temp;
        return dummyHead->next;
    }
};

注意： C++不要忘记释放临时节点。

面试题 02.07. 链表相交

题目链接： 面试题 02.07. 链表相交

【思路】

链表的长度不同，所以需要先统计两个链表的长度，然后将指针向前移动长度之差个节点，然后两个节点同时向前移动，指针相等时，即为相交，返回指针。

来自代码随想录
如图所示，首先设置curA指向链表A的头结点，curB指向链表B的头节点，然后将两个链表尾部对齐，curA移动到和curB对齐的位置，二者同时移动。

【代码】

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
         ListNode* curA = headA;
         ListNode* curB = headB;
         int sizeA = 0, sizeB = 0;
         while (curA != NULL) {
             curA = curA->next;
             sizeA++;
         }
         while (curB != NULL) {
             curB = curB->next;
             sizeB++;
         }
         curA = headA;
         curB = headB;
         
         //始终让curA指向较长的链表
         if (sizeA < sizeB) {
             swap (sizeA, sizeB);
             swap (curA, curB);
         }
         int n = sizeA - sizeB;
         while (n--) {
             curA = curA->next;
         }
         while (curA != NULL && curB != NULL) { //其实判断一个就行，因为最后剩的距离相等
             if (curA == curB) return curA;
             curA = curA->next;
             curB = curB->next;
         }
         return NULL;
    }
};

【注意】

节点的值相等不代表节点相等，相交指的是同一块内存，也就是指针指向的地址相等。

142.环形链表II

题目链接： 142.环形链表II

【思路】

此题比较难理解，必须借助画图来理解。
首先定义一组快慢指针，快指针一次走两个节点，慢指针一次走一个节点，二者一定会在环内相遇，因为在环内，就是快指针相对一个节点一个节点追慢指针的一个过程。
来自代码随想录

如果两个指针能够相遇，就一定证明有环，否则慢指针永远也追不上快指正。

在这里插入图片描述
相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头节点到环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
整理公式之后为如下公式：x = (n - 1) (y + z) + z
注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z
意味着：从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。
在相遇点定义一个index1，链表头部定义index2，两个指针同时向前移动，一次一个节点，在入口处相遇。

来自代码随想录

【代码】

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