Linked Lists in Go: Reversal and Length Calculation

Today's lesson will build upon our foundational understanding of linked lists by diving into practical implementation exercises using Go. These problems will sharpen your coding skills and prepare you for scenarios you might encounter in technical interviews.

Picture a scenario in which you have a sequence of events stored in a linked list. Your task is to look back in time — essentially, to reverse the chronology of these events. In technical terms, this means traversing a singly linked list in reverse order while keeping its structure intact. This skill is critical, whether for reversing transaction logs or simply navigating through a playlist from end to start.

Consider a browser's back-button functionality, where the most recently visited pages must be revisited in reverse order. This operation mirrors our task of reverse traversal in a linked list, capturing the essence of a real-world application. It’s crucial to differentiate between reverse traversal and reversing the linked list itself. For this problem, we essentially want to print out the elements in reverse order, keeping the structure intact.

Once approach to this problem can involve using a slice in Go. We navigate the linked list, storing the node values within the slice. Once the traversal is complete, we can extract the values in reverse by iterating over the slice backward.

Think of it like stacking books: each book (node value) goes sequentially into a stack, and then we iterate from the last added book to the first, "popping" them off one by one.

type ListNode struct {
    Value int
    Next  *ListNode
}

func ReversePrintLinkedList(head *ListNode) {
    // Use a slice to simulate stack behavior
    var stack []int

    // Traverse the linked list and append values to the slice
    for currentNode := head; currentNode != nil; currentNode = currentNode.Next {
        stack = append(stack, currentNode.Value)
    }

    // Iterate over the slice backward to simulate popping from a stack
    for i := len(stack) - 1; i >= 0; i-- {
        fmt.Println(stack[i])
    }
}

func main() {
    // Sample linked list: 1 -> 2 -> 3 -> nil
    head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
    ReversePrintLinkedList(head)
}

In this code, we utilize a slice called stack to store integers. As we traverse the linked list, each node's value is appended to stack. After collecting all values, we employ a reverse iteration to simulate the Last-In, First-Out (LIFO) order provided by stack operations. The solution has a time complexity of $O(n)$.