image.png

0. 链接

题目链接

1. 题目

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

2. 思路1：遍历统计总数量+遍历寻找旋转点

链表总长度为n的话, 则从右旋转k个位置后, 新的尾部下标为 n - 1 - k % n

3. 代码

# coding:utf8

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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

        n = 0
        curr_node = head
        tail_node = head
        while curr_node is not None:
            tail_node = curr_node
            n += 1
            curr_node = curr_node.next

        new_tail_idx = n - 1 - k % n
        i = 0
        curr_node = head
        while i != new_tail_idx:
            i += 1
            curr_node = curr_node.next

        new_tail = curr_node
        if new_tail != tail_node:
            tail_node.next = head
            new_head = new_tail.next
        else:
            new_head = head

        new_tail.next = None

        return new_head


def print_linked_list(head):
    array = []
    while head is not None:
        array.append(head.val)
        head = head.next

    print(array)


def create_linked_list(list):
    head = None
    node = None
    for val in list:
        if head is None:
            head = ListNode(val)
            node = head
        else:
            node.next = ListNode(val)
            node = node.next
    return head


def rotate_and_print(solution, list, k):
    head = create_linked_list(list)
    new_head = solution.rotateRight(head, k)
    print_linked_list(new_head)


solution = Solution()
rotate_and_print(solution, [1, 2, 3, 4, 5], 2)
rotate_and_print(solution, [0, 1, 2], 4)
rotate_and_print(solution, [], 0)
rotate_and_print(solution, [1], 0)
rotate_and_print(solution, [1], 1)

输出结果

[4, 5, 1, 2, 3]
[2, 0, 1]
[]
[1]
[1]

4. 结果

image.png