LeetCode: Reverse Linked List— Optimal Solution Explained

LeetCode: Reverse Linked List — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

Reversing a linked list is a fundamental computer science problem and a popular interview question. We will dive into the most optimal solution to reverse a linked list, illustrating the process step-by-step with the help of visuals.

We will guide you step by step, using clear visuals to demonstrate how the solution works with time complexity of O(n) and space complexity of O(1)

Intuition/Solution

The intuition behind reversing a linked list is to change the direction of the pointers between the nodes in the linked list. The most optimal solution for this problem is to traverse the linked list iteratively and, at each step, reverse the direction of the pointer from the current node to the previous node. To achieve this, you need to maintain three pointers: previous, current, and next.

Here’s the step-by-step process to reverse a linked list:

1. Initialize three pointers: previous (initially set to null), current (set to head), and next (initially set to null).
2. Traverse the linked list by iterating through the nodes. a. Set the next pointer to current.next (store the next node in the original list). b. Update the current.next pointer to point to the previous node (reverse the link between the current and previous nodes). c. Move the previous and current pointers one step forward: set previous to current, and set current to next.
3. When the traversal is complete, the previous pointer will be pointing to the new head of the reversed linked list.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, as we are traversing the linked list once. The space complexity is O(1) because we are only using a constant amount of extra space for the three pointers.

Step-by-Step Visual Guide

Example

prev = null
curr = 1

# First iteration
next = 2
1 → null
2 → 3 → 4 → 5 → null
prev = 1
curr = 2

# Second iteration
next = 3
2 → 1 → null
3 → 4 → 5 → null
prev = 2
curr = 3

# Third iteration
next = 4
3 → 2 → 1 → null
4 → 5 → null
prev = 3
curr = 4

# Fourth iteration
next = 5
4 → 3 → 2 → 1 → null
5 → null
prev = 4
curr = 5

# Fifth iteration
next = null
5 → 4 → 3 → 2 → 1 → null
prev = 5
curr = null

Implementation Code

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    curr = head

    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    return prev

Javascript

function reverseLinkedList(head) {
    let prev = null;
    let curr = head;

    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}