您现在的位置是：首页 >技术教程 >算法Day04 | 24. 两两交换链表中的节点， 19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II网站首页技术教程

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

题目链接:24. 两两交换链表中的节点
这是循环的步骤：dum->1->2->3变为dum->2->1->3

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dum = new ListNode(-1, head);//虚拟头节点
        ListNode* cur = dum;//遍历节点
        while (cur->next != nullptr && cur->next->next != nullptr) {//区分奇偶
            ListNode* tmp = cur->next;//保存1节点防止丢失
            ListNode* tmp2 = tmp->next->next;//保存3节点
            cur->next = cur->next->next;//dum->2
            cur->next->next = tmp;//2->1
            tmp->next = tmp2;//1->3
            cur = cur->next->next;//更新cur位置
        }
        return dum->next;
    }
};

            ListNode* tmp2 = tmp->next->next;//保存3节点
            cur->next = cur->next->next;//dum->2
            cur->next->next = tmp;//2->1
            tmp->next = tmp2;//1->3

不能换成

            cur->next = cur->next->next;//dum->2
            cur->next->next = tmp;//2->1
            tmp->next = tmp->next->next;//1->3

因为在2->1时，2和3已经断了，不能用tmp2和tmp以前的关系修改

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

题目链接： 19.删除链表的倒数第N个节点
用双指针来保持N的距离。当快指针指到nullptr，满指针所指的就位倒数第n个节点。但，删除当前节点，需要的是知道该节点的上一个节点才能操作。因此让快指针指到末尾节点，再对满指针操作。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dum = new ListNode(-1, head);
        ListNode* fast = dum;
        ListNode* slow = dum;
        while (n--) fast = fast->next;//快指针偷跑，保持快满指针的距离
        
        //根据1<=n<=sz，有快指针不会指向空指针，所以不需要有fast != null的条件
        while (fast->next != nullptr) {
            
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;//释放内存
        return dum->next;
    }
};

面试题 02.07. 链表相交

题目链接：面试题 02.07. 链表相交
相交不是数值相等，而是指针相等。
由题意得，让两个链表尾部对齐，可以便于比较相交部分。
比较长短之后，将长的链表设置为A链表，方便后续操作。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA, * curB = headB;//遍历链表

        //计算两个链表的长度
        int cntA = 0, cntB = 0;
        while (curA != nullptr) {
            curA = curA->next;
            cntA++;
        }
        while (curB != nullptr) {
            curB = curB->next;
            cntB++;
        }

        //重新指向头节点，遍历用
        curA = headA;
        curB = headB;

        //选择较长的链表为A链表
        if (cntA < cntB) {
            swap(cntA, cntB);
            swap(curA, curB);
        }

        //计算长度差，让长的链表对应的节点先跑
        int dis = cntA - cntB;
        while (dis--) {
            curA = curA->next;
        }

        while (curA != nullptr) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }

        return nullptr;
    }
};

142.环形链表II

题目链接：142.环形链表II
判断是否有环：有环，相当于一直在绕圈。速度不同，在圈中一定会相遇。因此选择双指针，快指针每次走两个节点，慢指针每次走一个节点。快指针相对慢指针为每次多走了一个节点（这很重要，只能是一个节点，移动了单位节点）

相遇的节点：慢指针走一圈的时间，快指针已经走了两圈了。快指针一定在慢指针没走完一圈的中途，遇到慢指针。所以慢指针没有完整的走过一遍环，就遇到了快指针。
快指针的速度 $v_{fast}=2$ 节点/次，慢指针速度 $v_{slow}=1$ 节点/次。
从起点到环入口的距离为 $x$ 个节点，从入口到第一次环中相遇的距离为 $y$ 个节点，从相遇位置到下一次环入口的距离为 $z$ 个节点。
有
$$\begin{array}{rl}{t}_{slow}& =t_{fast}\\ \frac{x+y}{1}& =\frac{x+y+n(y+z)}{2}\\ x& =n(y+z)-y\\ x& =(n-1)(y+z)+z\end{array}$$
其中 $n=1,2,\cdots$ 为快指针走的圈数。
上式表明，当相遇之后，以头节点和相遇处分别有两个1节点/次移动的节点，当两个节点相同时，找到了环入口节点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head, * slow = head;
        while (fast != nullptr && fast->next != nullptr/*fast是两个节点*/) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {
                ListNode* ptr1 = head, * ptr2 = fast;//用来计算相遇节点 x = z
                while (ptr1 != ptr2) {
                    ptr1 = ptr1->next;
                    ptr2 = ptr2->next;
                }
                return ptr1;
            }
        }
        return nullptr;
    }
};