leetcode 链接：旋转链表

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

解答 & 代码

时间复杂度 O(N)，空间复杂度 O(1)

/**
 * 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 {
private:
    // 计算链表长度
    int calListLen(ListNode* head)
    {
        int len = 0;
        ListNode* cur = head;
        while(cur != nullptr)
        {
            ++len;
            cur = cur->next;
        }
        return len;
    }

public:
    ListNode* rotateRight(ListNode* head, int k) {
        // 特殊情况：如果链表为空 or 只有一个节点 or k<=0，则无需旋转，直接返回头节点
        if(head == nullptr || head->next == nullptr || k <= 0)
            return head;

        int len = calListLen(head);        // 链表长度
        k = k % len;                    // 将 k 除链表长度取余
        if(k == 0)                        // 如果取余后 k = 0，说明无需旋转，直接返回头节点
            return head;

        ListNode* slow = head;
        ListNode* fast = head;
        for(int i = 0; i < k; ++i)        // 快指针先走 k 步
            fast = fast->next;
        // 快慢指针一起走，直到快指针走到最后一个非空节点，则慢指针走到倒数第 k-1 个节点
        while(fast->next != nullptr)    
        {
            slow = slow->next;
            fast = fast->next;
        }

        ListNode* newHead = slow->next;    // 倒数第 k 个节点就是旋转后链表的头节点
        slow->next = nullptr;            // 倒数第 k-1 个节点是旋转后链表的最后一个非空节点，将其next指向null
        fast->next = head;                // 连接原链表的尾部节点和头节点，组成旋转后的新链表

        return newHead;
    }
};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 39.68% 的用户
内存消耗：11.4 MB, 在所有 C++ 提交中击败了 33.19% 的用户