MediumNo. 0061

Rotate List — LeetCode 61 Python Solution

Topics
Linked List, Two Pointers
On a study list
Top Interview 150
Reading time
4 min

The problem

Given the head of a linked list, rotate the list to the right by k places.

Example

Input
head = [1,2,3,4,5], k = 2
Output
[4,5,1,2,3]

Python solution

PythonSolution
# 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: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        cur, n = head, 0
        while cur:
            n += 1
            cur = cur.next
        k %= n
        if k == 0:
            return head
        fast = slow = head
        for _ in range(k):
            fast = fast.next
        while fast.next:
            fast, slow = fast.next, slow.next

        ans = slow.next
        slow.next = None
        fast.next = head
        return ans

Complexity

Time
O(n)where n is the number of nodes in the linked list
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 61. Rotate List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 61. Rotate List?

LeetCode 61. Rotate List is rated Medium on LeetCode.

What is the time complexity of LeetCode 61. Rotate List?

The Python solution on this page runs in O(n), where n is the number of nodes in the linked list.

What is the space complexity of LeetCode 61. Rotate List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 61. Rotate List cover?

LeetCode 61. Rotate List is tagged Linked List and Two Pointers on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.