Data Structure And Algo6 min read
In-Place ReversalReverse LinkedLinked ListData Structure

In-Place Reversal of a Linked List: A Deep Dive

In-place reversal of a linked list is a crucial algorithm technique where you reverse the order of nodes in a linked list without using any extra space proportional to the list's size. This contrasts with approaches that create a new linked list to store the reversed sequence. The in-place nature makes it memory-efficient, especially for large lists.

Understanding the Technique

The core idea is to iteratively change the next pointers of the nodes. We'll traverse the list, modifying the pointers to redirect the links in reverse order. This involves manipulating three pointers:

  • current: Points to the currently processed node.
  • previous: Points to the node before current.
  • next: Temporarily stores the next pointer of current to prevent losing the connection.

Diagrammatic Representation:

Imagine a linked list: 1 -> 2 -> 3 -> 4 -> null

  1. Initially: previous = null, current = 1, next = 2.
  2. Reverse current's pointer: current.next = previous (1 -> null)
  3. Move pointers forward: previous = 1, current = 2, next = 3
  4. Repeat steps 2 & 3 until the end of the list is reached.

(The final state will be: 4 -> 3 -> 2 -> 1 -> null)


flowchart LR
    subgraph Step["Single In-Place Reversal Step"]
        direction LR
        P["prev (Node 1)"]
        C["current (Node 2)"]
        Nx["next (Node 3)"]
        C -->|1. Save next = current.next| Nx
        C -->|2. Flip pointer: current.next = prev| P
        Nx --> N4["Node 4 ..."]
    end


flowchart TD
    Start["prev = null, current = head"] --> WhileCheck{"current != null ?"}
    WhileCheck -- Yes --> Step1["next = current.next"]
    Step1 --> Step2["current.next = prev (Reverse link)"]
    Step2 --> Step3["prev = current (Advance prev)"]
    Step3 --> Step4["current = next (Advance current)"]
    Step4 --> WhileCheck
    WhileCheck -- No --> EndNode["head = prev
Return new head"]

Code Examples:

Java:

class Node {
    int data;
    Node next;
    Node(int d) {data = d; next = null;}
}

class LinkedList {
    Node head;

    void reverse() {
        Node prev = null;
        Node current = head;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    // ... (Methods to print and create LinkedList) ...
}

Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

    # ... (Methods to print and create LinkedList) ...

JavaScript:

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    reverse() {
        let prev = null;
        let current = this.head;
        while (current) {
            let next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }

    // ... (Methods to print and create LinkedList) ...
}

Identifying the Pattern in Algorithm Problems

Problem statements often hint at the need for in-place linked list reversal. Look for these indicators:

  • Reversal of a linked list: This is the most direct clue.
  • Space complexity constraints: Problems emphasizing constant space complexity (O(1)) strongly suggest an in-place approach.
  • Manipulation of pointers: If the problem involves modifying the next pointers of nodes, it likely involves in-place manipulation.
  • Palindrome check in a linked list: Reversing the second half of a linked list is a common technique for efficiently checking if it's a palindrome.

Tips and Tricks for Identification

  • Read carefully: Pay close attention to the problem statement's requirements and constraints.
  • Consider space complexity: If constant space is desired, an in-place algorithm is almost certainly needed.
  • Visualize the process: Draw diagrams to understand how pointer manipulations would reverse the list.

Mastering Algorithms: In-Place Reversal of a Linked List and Beyond

This blog post delves into the in-place reversal of a linked list, a fundamental algorithm in computer science. We'll explore the problem, its solution, and several related algorithmic challenges.

In-Place Reversal of a Linked List

In-place reversal means modifying the list directly without using extra space proportional to the list's size. This is crucial for optimizing memory usage, especially when dealing with large datasets.

Understanding the Pattern and Solution:

The key to in-place reversal is iteratively changing the next pointers of each node. We'll traverse the list, changing each node's pointer to point to the previous node. This requires tracking three pointers:

  1. current: The current node being processed.
  2. previous: The node before current.
  3. next: The node after current.

Step-by-Step Approach:

  1. Initialize previous to null, current to the head of the list.
  2. Iterate until current becomes null.
  3. For each node, store the next node in a temporary variable.
  4. Reverse the current node's next pointer to point to previous.
  5. Move previous one step forward (previous = current).
  6. Move current one step forward (current = next).

Code Examples:

Java:

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    void reverse() {
        Node prev = null, curr = head, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
    }
}

Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        curr = self.head
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        self.head = prev

JavaScript:

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    reverse() {
        let prev = null, curr = this.head, next = null;
        while (curr) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        this.head = prev;
    }
}

Example Problems:

  1. Palindrome Check: Determine if a linked list is a palindrome (reads the same forwards and backward).
  2. Nth Node from End: Find the Nth node from the end of a linked list.
  3. Merge Two Sorted Lists: Merge two sorted linked lists into a single sorted linked list.
  4. Detect Cycle: Determine if a linked list contains a cycle (loop).
  5. Remove Duplicates: Remove duplicate nodes from a sorted linked list.
  6. Find Middle Node: Find the middle node of a linked list.
  7. Intersection of Two Linked Lists: Find the intersection point of two linked lists.
  8. Reverse a Sublist: Reverse a portion of a linked list between given positions.
  9. Rotate a Linked List: Rotate a linked list by k positions.
  10. Add Two Numbers (represented as linked lists): Add two numbers represented as reversed linked lists.

Mastering Algorithms: In-Place Reversal of a Linked List

This blog post delves into the in-place reversal of a linked list, a common algorithmic problem encountered in software engineering. We'll explore different approaches, identify recurring patterns, and provide solutions in Java, Python, and JavaScript. We will also offer interview questions to test your understanding at various difficulty levels.

Understanding the Problem

The goal is to reverse a singly linked list without using extra space proportional to the list's length. This "in-place" constraint is crucial and distinguishes it from simpler reversal techniques that create a new list.

Identifying the Pattern

The key pattern involves iteratively manipulating the pointers of each node. We need to:

  1. Track the current node, the previous node, and the next node.
  2. Reverse the direction of the current node's pointer.
  3. Move the "previous" and "current" pointers forward.

Simple Approach: Iterative Reversal

This approach uses three pointers to achieve the reversal.

Java:

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

class LinkedList {
    Node head;

    void reverse() {
        Node prev = null, curr = head, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
    }
}

Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        curr = self.head
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        self.head = prev

JavaScript:

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    reverse() {
        let prev = null, curr = this.head, next = null;
        while (curr) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        this.head = prev;
    }
}

Diagram:

Imagine a list: 1 -> 2 -> 3 -> 4 -> NULL

The iterative process will change the pointers as follows:

  1. Initially: prev = NULL, curr = 1, next = 2
  2. Iteration 1: curr.next = prev (1->NULL), prev = 1, curr = 2
  3. Iteration 2: curr.next = prev (2->1), prev = 2, curr = 3
  4. Iteration 3: curr.next = prev (3->2), prev = 3, curr = 4
  5. Iteration 4: curr.next = prev (4->3), prev = 4, curr = NULL
  6. head = prev (head = 4)

Interview Questions (Difficulty Levels)

Easy:

  1. Reverse a linked list with only one node.
  2. Reverse a linked list with two nodes.
  3. Given a linked list, write a function to check if it's already reversed.

Medium:

  1. Reverse a linked list from a given position m to n.
  2. Reverse a linked list in groups of k.

Hard:

  1. Reverse a linked list in-place using recursion. (More challenging due to stack space usage, but still considered in-place).
  2. Reverse k nodes in a linked list, recursively, without using extra space.
  3. Reverse a linked list using only constant extra space, and without changing the values of the nodes themselves. (This is more of a conceptual challenge, focusing on pointer manipulation).

Example Problems

  1. Reverse a linked list to create a palindrome.
  2. Find the middle node of a linked list and reverse the second half.
  3. Given two sorted linked lists, merge them into a single sorted linked list after reversing the first list.
  4. Check if a linked list is a palindrome.
  5. Reverse alternate k nodes in a linked list.
  6. Reverse every alternate k nodes in a linked list recursively.

Related Guides:
← PreviousFast and Slow Pointers: Cycle Detection & InvariantsNext →K-Way Merge Pattern: Heaps, Streams & External Sorting