NUHMAN.com

Introduction

LeetCode 61: Rotate List is a classic problem that challenges your understanding of linked list manipulations. The problem asks you to rotate a linked list to the right by k places, which means moving the last k nodes to the front of the list.

This problem tests your ability to work with linked lists, efficiently handle circular references, and think about the list's structure during rotation.

Problem Statement

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

Example 1:

go

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

Example 2:

go

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

Constraints

• The number of nodes in the list is in the range [0, 5000].
• -100 <= Node.val <= 100
• 0 <= k <= 10^5

Approach:

The key to solving this problem efficiently is recognizing the structure of the linked list and how to rotate it without re-arranging the nodes repeatedly.

Steps:

1. Find the length of the linked list.
2. Connect the tail of the list to the head, forming a circular linked list.
3. Calculate the effective number of rotations as k % length because rotating the list by the list’s length results in the same list.
4. Find the new tail of the list at position length - k % length - 1.
5. Break the circular connection and set the new head.

Go Implementation

go

type ListNode struct {
    Val  int
    Next *ListNode
}

func rotateRight(head *ListNode, k int) *ListNode {
    // Edge case: if the list is empty or has only one element
    if head == nil || head.Next == nil || k == 0 {
        return head
    }

    // Step 1: Find the length of the list and the tail node
    length := 1
    tail := head
    for tail.Next != nil {
        tail = tail.Next
        length++
    }

    // Step 2: Find the effective number of rotations needed
    k = k % length
    if k == 0 {
        return head
    }

    // Step 3: Connect the tail to the head to form a circular list
    tail.Next = head

    // Step 4: Find the new tail, which is (length - k % length - 1) nodes away
    newTail := head
    for i := 0; i < length - k - 1; i++ {
        newTail = newTail.Next
    }

    // Step 5: Break the circular connection and set the new head
    newHead := newTail.Next
    newTail.Next = nil

    return newHead
}

Example Walkthrough

For input head = [1,2,3,4,5] and k = 2:

1. Find the length: The linked list has a length of 5.
2. Effective rotations: k % 5 = 2.
3. Connect the tail to the head: Create a circular list [1 → 2 → 3 → 4 → 5 → 1 → 2 → ...].
4. Find the new tail: Move 3 steps to find the new tail, which is 3 → 4 → 5 → 1 → 2.
5. Break the cycle: Set the new head to 4 and return the new list [4 → 5 → 1 → 2 → 3].

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: O(n) because we need to traverse the entire list to compute its length and find the new tail.
• Space Complexity: O(1) since we use constant space and manipulate the pointers in-place.

Edge Cases

1. Empty list (head == nil): Return nil immediately.
2. Single element list (head.Next == nil): No rotation is needed.
3. k = 0: Return the original list, as no rotation is needed.
4. k > length of the list: We handle this by using k % length to avoid unnecessary rotations.

Key Takeaways

• Circular Linked List: By connecting the tail to the head, we can easily find the new head by adjusting the pointers.
• Efficient modular arithmetic (k % length) reduces unnecessary rotations.
• Pointer manipulation is the key to solving this problem with constant space.