Solving Rotate List in Go: Step-by-Step Guide

Introduction to Rotate List in Go

The Rotate List problem is a classic linked list challenge frequently encountered in coding interviews and algorithm practice. The task is straightforward: given the head of a singly linked list and a non-negative integer k, rotate the list to the right by k places. Despite its apparent simplicity, this problem tests your understanding of linked list traversal, pointer manipulation, and edge case handling.

In this tutorial, we will walk through the problem step by step, build a complete solution in Go, and discuss best practices that will help you write clean, efficient, and interview-ready code.

What Is the Rotate List Problem?

Rotating a list to the right by k places means moving the last k nodes to the front of the list. For example, consider the following linked list:

1 -> 2 -> 3 -> 4 -> 5

If we rotate this list to the right by k = 2, the result is:

4 -> 5 -> 1 -> 2 -> 3

The last two nodes (4 and 5) are moved to the front, and the remaining nodes follow in their original order. If k is larger than the length of the list, the rotation wraps around. For instance, rotating a list of length 5 by k = 7 is equivalent to rotating it by k = 2, because 7 % 5 = 2.

Formal Problem Statement

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

Why It Matters

The Rotate List problem matters for several reasons:

• Linked list mastery: It reinforces your ability to traverse, count, and rewire pointers in a singly linked list — skills that transfer to many other data structure problems.
• Edge case awareness: The problem forces you to consider empty lists, single-node lists, k = 0, and k larger than the list length.
• Interview relevance: It is a popular problem on platforms like LeetCode (problem #61) and frequently appears in technical interviews at major tech companies.
• Real-world analogues: Rotation operations appear in circular buffers, round-robin scheduling, and ring buffer implementations used in networking and embedded systems.

Defining the Linked List Node in Go

Before solving the problem, we need to define the structure of a linked list node. In Go, this is typically done using a struct:

package main

import "fmt"

// ListNode represents a node in a singly linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

The ListNode struct contains an integer value Val and a pointer Next to the subsequent node. This is the foundation upon which our solution will be built.

Step-by-Step Approach

To solve this problem efficiently, we can break it down into a series of clear steps:

Step 1: Handle Edge Cases

If the list is empty (head == nil), contains a single node (head.Next == nil), or k == 0, no rotation is needed. We can return the head immediately.

Step 2: Compute the Length of the List

We traverse the entire list to count the number of nodes. While doing so, we also keep a reference to the tail node, which we will need later to close the list into a ring.

Step 3: Normalize k

Since rotating a list of length n by n positions results in the same list, we compute k = k % n. If the result is 0, no rotation is needed, and we return the head as-is.

Step 4: Find the New Tail

The new tail of the rotated list is the node at position n - k - 1 (using zero-based indexing). We traverse from the head to this node. The node immediately after it becomes the new head.

Step 5: Rewire the Pointers

We perform the following pointer operations:

• Connect the old tail's Next to the old head, forming a circular list.
• Set the new tail's Next to nil, breaking the circle.
• Return the new head.

Complete Go Implementation

Here is the full implementation of the Rotate List solution in Go:

package main

import "fmt"

// ListNode represents a node in a singly linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// rotateRight rotates the linked list to the right by k places.
func rotateRight(head *ListNode, k int) *ListNode {
    // Step 1: Handle edge cases
    if head == nil || head.Next == nil || k == 0 {
        return head
    }

    // Step 2: Compute the length and find the tail
    length := 1
    tail := head
    for tail.Next != nil {
        tail = tail.Next
        length++
    }

    // Step 3: Normalize k
    k = k % length
    if k == 0 {
        return head
    }

    // Step 4: Find the new tail (at position length - k - 1)
    newTail := head
    for i := 0; i < length-k-1; i++ {
        newTail = newTail.Next
    }

    // The new head is the node after the new tail
    newHead := newTail.Next

    // Step 5: Rewire the pointers
    tail.Next = head   // Connect old tail to old head (form a ring)
    newTail.Next = nil // Break the ring at the new tail

    return newHead
}

// helperList builds a linked list from a slice of integers.
func helperList(vals []int) *ListNode {
    if len(vals) == 0 {
        return nil
    }
    head := &ListNode{Val: vals[0]}
    current := head
    for i := 1; i < len(vals); i++ {
        current.Next = &ListNode{Val: vals[i]}
        current = current.Next
    }
    return head
}

// printList prints the linked list values in order.
func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d", head.Val)
        if head.Next != nil {
            fmt.Printf(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

func main() {
    // Example 1
    list1 := helperList([]int{1, 2, 3, 4, 5})
    fmt.Print("Original: ")
    printList(list1)
    rotated1 := rotateRight(list1, 2)
    fmt.Print("Rotated by 2: ")
    printList(rotated1)

    // Example 2
    list2 := helperList([]int{0, 1, 2})
    fmt.Print("Original: ")
    printList(list2)
    rotated2 := rotateRight(list2, 4)
    fmt.Print("Rotated by 4: ")
    printList(rotated2)

    // Example 3: edge case with empty list
    rotated3 := rotateRight(nil, 3)
    fmt.Print("Rotated empty list: ")
    printList(rotated3)
}

Expected Output

Original: 1 -> 2 -> 3 -> 4 -> 5
Rotated by 2: 4 -> 5 -> 1 -> 2 -> 3
Original: 0 -> 1 -> 2
Rotated by 4: 2 -> 0 -> 1
Rotated empty list:

How the Algorithm Works in Detail

Let us trace through the first example to understand the mechanics. The input list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2.

First, we traverse the list and discover that the length is 5, and the tail is the node with value 5. We normalize k as 2 % 5 = 2, which is non-zero, so we proceed.

Next, we find the new tail by moving length - k - 1 = 5 - 2 - 1 = 2 steps from the head. Starting at node 1, we move two steps to reach node 3. Node 3 is the new tail, and node 4 (its Next) is the new head.

We then connect the old tail (5) to the old head (1), forming a circular list: 1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> .... Finally, we break the circle by setting newTail.Next = nil, which gives us 4 -> 5 -> 1 -> 2 -> 3.

Complexity Analysis

Understanding the time and space complexity of your solution is essential, especially in interview settings.

• Time complexity: O(n) — We traverse the list twice: once to compute the length and find the tail, and once to find the new tail. Each traversal is linear in the number of nodes, so the overall time complexity is O(n).
• Space complexity: O(1) — We only use a fixed number of pointers (tail, newTail, newHead) regardless of the input size. No additional data structures are allocated.

This makes the solution optimal for the problem, as we cannot do better than O(n) time (we must at least read the input), and O(1) space is the best we can achieve.

Best Practices

When implementing the Rotate List solution or similar linked list problems, keep the following best practices in mind:

• Always handle edge cases first: Empty lists, single-node lists, and zero rotations should be caught early to avoid unnecessary work and potential nil pointer dereferences.
• Normalize k early: Computing k % length prevents unnecessary full rotations and protects against very large values of k that could cause excessive traversal.
• Use descriptive variable names: Names like newTail and newHead make the code self-documenting and easier to reason about during interviews.
• Draw the list on paper: Visualizing the pointer connections before writing code helps prevent off-by-one errors, especially when determining the position of the new tail.
• Test with multiple inputs: Verify your solution with normal cases, k larger than the list length, k equal to the list length, and edge cases like empty and single-node lists.
• Avoid modifying the list unnecessarily: The only pointer changes needed are connecting the tail to the head and breaking the list at the new tail. Extra modifications can introduce bugs.

Common Pitfalls to Avoid

Even experienced developers can make mistakes with this problem. Here are some common pitfalls:

• Forgetting to normalize k: If k is very large (for example, 200 million), traversing the list that many times would be catastrophically slow. Always use the modulo operation.
• Off-by-one errors when finding the new tail: The new tail is at position length - k - 1, not length - k. Mixing these up shifts the rotation by one position.
• Not breaking the circular connection: Forgetting to set newTail.Next = nil leaves the list in a circular state, which causes infinite loops when printing or traversing.
• Returning the wrong head: Make sure to return newHead, not the original head. The original head is no longer the first node after rotation.

Alternative Approach: Two-Pointer Technique

Another way to solve this problem is using the two-pointer technique. The idea is to use a fast pointer and a slow pointer, both starting at the head. The fast pointer moves k steps ahead first. Then both pointers move together until the fast pointer reaches the last node. At that point, the slow pointer is at the new tail.

func rotateRightTwoPointer(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }

    // First pass: find the length
    length := 1
    tail := head
    for tail.Next != nil {
        tail = tail.Next
        length++
    }

    k = k % length
    if k == 0 {
        return head
    }

    // Use two pointers
    fast := head
    for i := 0; i < k; i++ {
        fast = fast.Next
    }

    slow := head
    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }

    newHead := slow.Next
    slow.Next = nil
    tail.Next = head

    return newHead
}

This approach has the same time and space complexity as the first solution but demonstrates a different way of thinking about the problem. The two-pointer technique is a valuable tool that applies to many linked list problems, so it is worth practicing.

Conclusion

The Rotate List problem is an excellent exercise for strengthening your linked list manipulation skills in Go. By breaking the problem into manageable steps — handling edge cases, computing the length, normalizing k, finding the new tail, and rewiring pointers — you can arrive at a clean and efficient O(n) time, O(1) space solution. Remember to always test your code against edge cases, normalize k to avoid unnecessary work, and visualize the pointer connections before writing code. With these techniques and best practices in your toolkit, you will be well-prepared to tackle this problem and similar linked list challenges in both interviews and real-world development.