leetcode题解61：旋转链表

描述

分析

思路非常简单，将首尾相连，然后将head指向第n-k个结点的next结点，最后将第n - k个结点的next指向NULL；当然注意到k可能大于n，对令k = k % n就好了；比如下面这个例子：

1 -> 2 -> 3 -> 4 -> 5

当k=1时，首先首尾相连得到

1 -> 2 -> 3 -> 4 -> 5
^                   |
|-------------------

然后找到第4个结点，并将head指向该结点的next结点，然后将该结点的next指向NULL

1 -> 2 -> 3 -> 4  5 <-head
^                 |
|-----------------

这样链表不就变为了

5 -> 1 -> 2 -> 3 -> 4

代码

python

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or k == 0:
            return head

        last_node = head
        num_nodes = 1
        while last_node.next != None:
            last_node = last_node.next
            num_nodes += 1

        last_node.next = head
        for _ in range(num_nodes-k % num_nodes):
            last_node = last_node.next

        head = last_node.next
        last_node.next = None
        return head