熊二 | c++ | #调整牛群顺序#

题目考查的知识点

• 快慢指针
• 链表断链与重组

题目解答方法的文字解析

1. 初始化快慢指针，使用一个虚拟节点作为头节点（以便应对 n等于链表长度的情况）
2. 快指针先走n步
3. 快慢指针同时走，直到快指针指向最后一个节点
4. 这时候，慢指针的next指向了倒数第n个节点
5. 断链，因为要将该节点移动到链表尾部，所以该节点的next是需要置空

本题解析所用的编程语言

• c++

完整且正确的编程代码

class Solution {
public:
    ListNode* moveNthToEnd(ListNode* head, int n) {
        // 特判n=1的情况
        if(n==1)return head;

        // 1. 初始化快慢指针
        ListNode dummyHead = ListNode(-1);
        dummyHead.next = head;
        ListNode*fast=&dummyHead, *slow=&dummyHead;

        // 2. 快指针先走n步
        for(int i=1; i<=n; ++i)fast = fast->next;

        // 3. 快慢指针同时走
        while(fast&&fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        // 4. 这时候，慢指针的next指向了倒数第n个节点
        ListNode*node = slow->next;
        slow->next = slow->next->next;
        fast->next = node;

        // 5. 断链
        node->next = nullptr;

        return dummyHead.next;
    }
};