#61

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Rotate List

Rotate a singly linked list to the right by k positions using careful pointer manipulation and two-pointer traversal techniques.

linked list two pointers

Problem Statement

Given the head of a singly linked list and an integer k, rotate the list to the right by k places. Each rotation moves the last node to the front, repeated k times effectively.

For example, given head = [1,2,3,4,5] and k = 2, the rotated list becomes [4,5,1,2,3]. Another case: head = [0,1,2], k = 4 results in [2,0,1]. Handle empty lists and k larger than the list length carefully.

Examples

Example 1

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

Output: [4,5,1,2,3]

Example details omitted.

Example 2

Input: head = [0,1,2], k = 4

Output: [2,0,1]

Example details omitted.

Constraints

The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109

Solution Approach

Calculate list length and normalize k

Traverse the linked list to find its length n. Since rotating by k and k+n are equivalent, compute k modulo n to reduce unnecessary rotations.

Use two-pointer technique to locate new tail

Maintain two pointers separated by k nodes. Move both simultaneously until the front pointer reaches the end. The trailing pointer will mark the new tail after rotation.

Reconnect nodes to perform rotation

Link the old tail to the old head to form a temporary cycle, then break the link after the new tail. Update the head to the node after the new tail to complete rotation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because the list is traversed to find its length and then to relocate pointers. Space complexity is O(1) since no extra structures are needed beyond a few pointers.

What Interviewers Usually Probe

Expect correct pointer updates without creating cycles or losing nodes.
Check handling of k values larger than the list length.
Look for proper empty list and single-node edge case handling.

Common Pitfalls or Variants

Common pitfalls

Not using modulo for k, leading to extra unnecessary rotations.
Incorrectly updating the tail node, causing cycles or null references.
Failing to handle lists with length 0 or 1 properly.

Follow-up variants

Rotate list to the left by k positions instead of right.
Rotate a doubly linked list using similar pointer adjustments.
Rotate only a subsegment of the list rather than the entire list.

FAQ

What is the most efficient way to rotate a linked list by k positions?

Use a two-pointer approach to locate the new tail and adjust pointers, computing k modulo list length to avoid unnecessary rotations.

How do I handle k values larger than the linked list length?

Calculate k modulo n, where n is the length of the list, since rotating by n or multiples of n results in the same list.

Can I rotate an empty or single-node list?

Yes, the list remains unchanged, but ensure your code handles these edge cases without null pointer errors.

Why does the two-pointer technique help in Rotate List?

It allows locating the rotation point efficiently without multiple traversals, preventing broken links or cycles.

What are common mistakes when implementing Rotate List?

Failing to update the tail correctly, not using modulo for k, and mishandling empty or single-node lists are the main pitfalls.

terminal

Solution

Solution 1: Fast and Slow Pointers + Link List Concatenation

First, we check whether the number of nodes in the linked list is less than $2$. If so, we directly return $head$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

# 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

Continue Practicing

#82 remove duplicates from sorted list ii #86 partition list #19 remove nth node from end of list