61. 旋转链表

题目描述

输入链表头节点 head 和非负整数 k。链表用数组表示，例如 [1,2,3]。

把链表向右旋转 k 次。每旋转一次，就把最后一个节点摘下来，接到链表最前面。

返回旋转后链表的头节点。空链表直接返回空。

示例 1

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

解释：旋转 1 次得 [5,1,2,3,4]，再旋转 1 次得 [4,5,1,2,3]。

示例 2

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

解释：长度为 3，旋转 3 次回到原样，所以 4 次等于旋转 1 次，得 [2,0,1]。

数据范围

节点数在 [0, 500] 范围内。
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

解题思路

先走到尾节点并数出长度 n。向右旋转 n 次等于没动，所以只需旋转 k % n 次。把尾节点接到头上形成环，再从 head 走 n - k - 1 步到新的尾节点，它的下一个就是新头。在新尾节点处断开环即可。

为什么正确

形成环以后，从 head 出发走 j 步到达的是原链表下标 j 的节点；新尾节点是下标 n - k - 1，新头是下标 n - k。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

k 可能远大于长度，必须先取 k % n，否则会超时；k % n == 0 时要直接返回，不要成环。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        n, tail = 1, head
        while tail.next:
            tail = tail.next
            n += 1
        k %= n
        if k == 0:
            return head
        tail.next = head
        newTail = head
        for _ in range(n - k - 1):
            newTail = newTail.next
        newHead = newTail.next
        newTail.next = None
        return newHead

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        int n = 1; ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        k %= n;
        if (k == 0) {
            return head;
        }
        tail.next = head;
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next) {
            return head;
        }
        int n = 1; ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            n++;
        }
        k %= n;
        if (k == 0) {
            return head;
        }
        tail->next = head;
        ListNode* newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail->next;
        }
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        return newHead;
    }
};

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	n, tail := 1, head
	for tail.Next != nil {
		tail = tail.Next
		n++
	}
	k %= n
	if k == 0 {
		return head
	}
	tail.Next = head
	newTail := head
	for i := 0; i < n-k-1; i++ {
		newTail = newTail.Next
	}
	newHead := newTail.Next
	newTail.Next = nil
	return newHead
}

var rotateRight = function(head, k) {
    if (!head || !head.next) {
        return head;
    }
    let n = 1, tail = head;
    while (tail.next) {
        tail = tail.next;
        n++;
    }
    k %= n;
    if (k === 0) {
        return head;
    }
    tail.next = head;
    let newTail = head;
    for (let i = 0; i < n - k - 1; i++) {
        newTail = newTail.next;
    }
    const newHead = newTail.next;
    newTail.next = null;
    return newHead;
};

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (!head || !head.next) {
        return head;
    }
    let n = 1, tail = head;
    while (tail.next) {
        tail = tail.next;
        n++;
    }
    k %= n;
    if (k === 0) {
        return head;
    }
    tail.next = head;
    let newTail = head;
    for (let i = 0; i < n - k - 1; i++) {
        newTail = newTail.next;
    }
    const newHead = newTail.next;
    newTail.next = null;
    return newHead;
}

载入编辑器，自己跑一遍 →

链表专题的其他题目

查看链表全部题目 →