NUHMAN.com

Problem Statement

Given the head of a singly linked list, reverse the list and return its head.

Function Signature:

go

func reverseList(head *ListNode) *ListNode

Example 1:

go

head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
head.Next.Next.Next.Next = &ListNode{Val: 5}

fmt.Println(reverseList(head)) 
// Output: [5, 4, 3, 2, 1]

Explanation: The linked list is reversed, so the order is [5, 4, 3, 2, 1].

Example 2:

go

fmt.Println(reverseList(nil)) 
// Output: nil

Explanation: An empty list is reversed and remains empty.

Constraints:

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

Approach

To reverse a singly linked list, we need to iteratively traverse the list and reverse the direction of the pointers. This can be done using three pointers:

1. Previous Pointer: This will point to the previous node in the list.
2. Current Pointer: This will point to the current node being processed.
3. Next Pointer: This will point to the next node to prevent losing the rest of the list.

Steps:

1. Start by setting the previous pointer to nil and the current pointer to the head of the list.
2. Traverse the list while the current pointer is not nil:

• Store the next node (next).
• Reverse the link by pointing current.Next to previous.
• Move the previous pointer to current, and the current pointer to next.

1. Once the traversal is complete, the previous pointer will point to the new head of the reversed list.

Time Complexity:

• O(n), where n is the number of nodes in the linked list. We visit each node once.

Space Complexity:

• O(1), since we are only using a constant amount of space (3 pointers) regardless of the size of the input list.

Go Implementation

go

package main

import "fmt"

// ListNode is the structure of a node in the singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// Function to reverse the linked list
func reverseList(head *ListNode) *ListNode {
    var previous *ListNode = nil
    current := head
    
    // Traverse the list and reverse the links
    for current != nil {
        next := current.Next    // Store the next node
        current.Next = previous // Reverse the current node's pointer
        previous = current      // Move previous to the current node
        current = next          // Move to the next node
    }
    
    return previous // At the end, previous will be the new head of the reversed list
}

// Helper function to print the linked list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

func main() {
    // Example 1: Create a linked list [1, 2, 3, 4, 5]
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}

    fmt.Println("Original List:")
    printList(head)

    // Reverse the linked list
    reversedHead := reverseList(head)
    
    fmt.Println("Reversed List:")
    printList(reversedHead)

    // Example 2: Reverse an empty linked list
    fmt.Println("Reversed Empty List:")
    printList(reverseList(nil)) // Output: nil
}

Explanation of the Code:

1. ListNode Structure:

• We define a ListNode struct which represents a node in a singly linked list. Each node contains a value (Val) and a pointer to the next node (Next).

2. reverseList Function:

• Input: The function takes the head of the linked list as an argument.
• Initialization: We initialize two pointers:
• previous is set to nil (this will be the new tail of the list).
• current is set to head (this will traverse through the list).
• Traversal & Reversal: We iterate through the list:
• For each node, we store the next node to avoid losing reference to the rest of the list.
• We then reverse the link by setting current.Next to previous.
• Move previous to current and current to next.
• Return: Once the traversal is complete, previous will be the new head of the reversed list, which we return.

3. Helper Function printList:

• This function is used to print the values of the linked list nodes in order, so we can visualize the list before and after reversal.

4. Main Function:

• The main function demonstrates how to create a linked list, reverse it, and print the results.

Example Walkthrough

Example 1:

Input:

go

head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
head.Next.Next.Next.Next = &ListNode{Val: 5}

The linked list is:

rust

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

• Step 1: The current pointer starts at 1, and the previous pointer is nil.
• Step 2: The next pointer stores the next node (2). We reverse the link so that 1 now points to nil.
• Step 3: Move previous to 1 and current to 2. Repeat the process until the current pointer reaches nil.
• Step 4: The reversed list is:

rust

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

Output:

yaml

Reversed List: 5 4 3 2 1

Example 2:

Input:

go

printList(reverseList(nil)) 

For an empty list (nil), the function returns nil, and the output is:

mathematica

Reversed Empty List: 

Conclusion

The LeetCode 206: Reverse Linked List problem is a fundamental problem that can be solved efficiently using an iterative approach with three pointers. The space complexity is O(1), and the time complexity is O(n), where n is the number of nodes in the list. This is an optimal solution for this problem.