61. 旋转链表(Medium)

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

样例

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
# k 向右移动了4，相当于向右移动了 4%3 = 1 个单位

Python示例

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next: 
            return head 
            
        n = 0
        p = head 
        while p:
            if not p.next:
                end = p 
            n += 1
            p = p.next 
            
        end.next = head  # 连成环
        k = k % n 

        p = head 
        for _ in range(n - k - 1): # n - k 个
            p = p.next 
        res = p.next 
        p.next = None 
        return res