0061. Rotate List.md

C++

/**
 * 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) return head;

        ListNode* slow = head;
        ListNode* fast = head;
        int length = 0;

        while(fast) {
            fast = fast->next;
            length += 1;
        }

        fast = head;
        k %= length;

        while(k) {
            fast = fast->next;
            k--;
        }

        while(fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        fast->next = head;
        head = slow->next;
        slow->next = nullptr;

        return head;
    }
};

Time Complexity: O(n)
Space Complexity: O(1)

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if(!head) return head;
    let curr = head, count = 0;
    
    while(curr) {
        count++;
        curr = curr.next;
    }
    
    k = k % count;
    let prev = head;
    curr = head;
    
    while(k) {
        curr = curr.next;
        k--;
    }
    
    while(curr.next) {
        prev = prev.next;
        curr = curr.next;
    }
    curr.next = head;
    head = prev.next;
    prev.next = null;
    return head;
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head;

        // 1. dummy
        ListNode dummy(0);
        dummy.next = head;

        // 2. 计算长度
        int len = 0;
        ListNode* tail = head;
        while (tail) {
            len++;
            if (!tail->next) break;
            tail = tail->next;
        }

        k %= len;
        if (k == 0) return head;

        // 3. 快慢指针
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        // fast 先走 k 步
        for (int i = 0; i < k; i++) {
            fast = fast->next;
        }

        // 一起走到 fast 指向尾结点
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }

        // 4. 旋转
        ListNode* newHead = slow->next;
        slow->next = nullptr;
        fast->next = dummy.next;

        return newHead;
    }
};