Solving the LeetCode "Rotate List" Problem in Go

Difficulty: Medium | Tags: Linked List, Two Pointers

Introduction

Rotating a linked list involves shifting the list's nodes to the right by a given number of positions. This problem tests understanding of linked list manipulation and efficient traversal techniques.

Problem Analysis

The task is to rotate a linked list to the right by k places. For example, rotating [1,2,3,4,5] by 2 results in [4,5,1,2,3]. If k is larger than the list length, we take k modulo the list length to avoid unnecessary rotations.

Solution Approach

1. Find the length of the linked list.
2. Adjust k to be within the list length using modulo.
3. Find the new head by traversing to the (length - k)th node.
4. Break the list at this point and connect the end to the original head.

Go Implementation

/**
* Definition for singly-linked list.
* type ListNode struct {
    *     Val int
    *     Next *ListNode
    * }
    */
    func rotateRight(head *ListNode, k int) *ListNode {
        if head == nil || head.Next == nil || k == 0 {
            return head
        }
        // Step 1: Find the length of the list
        length := 1
        tail := head
        for tail.Next != nil {
            tail = tail.Next
            length++
        }
        // Step 2: Adjust k to be within the list length
        k = k % length
        if k == 0 {
            return head
        }
        // Step 3: Find the new tail (length - k - 1 steps from head)
        newTail := head
        for i := 0; i < length - k - 1; i++ {
            newTail = newTail.Next
        }
        // Step 4: Break the list and reconnect
        newHead := newTail.Next
        newTail.Next = nil
        tail.Next = head
        return newHead
    }

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We traverse the list twice: once to find the length and once to find the new tail.
Space Complexity: O(1), as we use a constant amount of extra space.

Testing and Examples

Test Case 1: head = [1,2,3,4,5], k = 2 → Output: [4,5,1,2,3]
Test Case 2: head = [0,1,2], k = 4 → Output: [2,0,1]
Edge Case: head = [], k = 0 → Output: []

Best Practices and Tips

1. Always handle edge cases like empty lists or single-node lists.
2. Use modulo to handle large k values efficiently.
3. Visualize the list rotation to better understand the pointer manipulation.