Link to LeetCode Problem

S1: 直觉思路

直观的思路就是将末尾的 k 个节点移到头部。

• 第一步是找到倒数第 k - 1 个节点，不会的可以先看 剑指 Offer 22. 链表中倒数第k个节点
• 接下来就是简单的链表指针操作罢了，将 [0, k-1] 和 [k, n-1] 这两段链表换个位置。
• 由于 k 可能会大于链表长度，所以我们最好先计算出链表长度再取模。
• 既然已经知道了链表长度，第一步也可以不使用双指针来找倒数 k -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 {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) return head;

        int n = 0;
        ListNode* p = head;
        ListNode* oldTail;
        // 先计算出链表的长度，顺便记录下链表原尾部
        while (p != nullptr) {
            if (p->next == nullptr) oldTail = p;
            p = p->next;
            n++;
        }
        if (k % n == 0) return head;
        // 找倒数第 k-1 个节点
        k = n - k % n - 1;
        p = head;
        // 找到分割点，p 是新尾部，p->next 是新头部
        while (k-- > 0) {
            p = p->next;
        }
        if (p->next == nullptr) return head;
        // 穿针引线将两段链表换个位置
        ListNode* newTail = p;
        ListNode* newHead = p->next;
        newTail->next = nullptr;
        oldTail->next = head;
        return newHead;
    }
};

• Time: $O(N)$
• Space: $O(1)$

S2: 闭环

将链表首尾相连，从原尾部开始走 n-k 步，断开。相比第一种解法，少了操作链表指针的繁琐操作。

/**
 * 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* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) return head;

        int n = 1;
        ListNode* p = head;
        while (p->next != nullptr) {
            p = p->next;
            n++;
        }
        // 首尾相连
        p->next = head;
        k = n - k % n;
        // 走 n-k 步，断开
        while (k-- > 0) {
            p = p->next;
        }
        ListNode* newHead = p->next;
        p->next = nullptr;
        return newHead;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
    if (!head || k === 0) return head;

    let cur = head,
        len = 1;
    while (cur.next) {
        cur = cur.next;
        len++;
    }
    cur.next = head;

    cur = head;
    let n = len - (k % len) - 1;
    while (n > 0) {
        cur = cur.next;
        n--;
    }
    const newHead = cur.next;
    cur.next = null;
    return newHead;
};

• Time: $O(N)$
• Space: $O(1)$