Overview

Reversing a linked list is a fundamental question in data structure interviews, focusing on understanding and manipulating the pointers in a linked list. This operation is essential for demonstrating proficiency in linked lists, a basic yet critical data structure, and showcases an understanding of pointer manipulation and in-place list modification techniques.

Key Concepts

1. Pointer Manipulation: Understanding how node pointers work and how to change their direction.
2. In-place Reversal: Modifying the list without using additional data structures.
3. Recursive vs Iterative Solutions: Knowing both approaches and when to use each.

Common Interview Questions

Basic Level

1. How do you reverse a singly linked list iteratively?
2. Can you reverse a linked list using recursion?

Intermediate Level

3. How would you reverse a portion of a linked list from position m to n?

Advanced Level

4. Discuss the space and time complexity of your linked list reversal algorithm. Can it be optimized further?

Detailed Answers

1. How do you reverse a singly linked list iteratively?

Answer: To reverse a singly linked list iteratively, you maintain three pointers (previous, current, and next) to track and reverse the node connections in a single pass. Initially, previous is set to null, and current is set to the head of the list. As you iterate through the list, you adjust the pointers to reverse the link direction of each node.

Key Points:
- Initialization: Start with previous set to null and current to the head.
- Iteration: Move through the list, reversing pointers.
- Termination: The operation ends when current reaches the end of the list.

Example:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next; // Save next node
            current.next = previous; // Reverse current node's pointer
            previous = current; // Move pointers one position ahead.
            current = nextTemp;
        }
        return previous; // New head of the reversed list
    }
}

2. Can you reverse a linked list using recursion?

Answer: Yes, reversing a linked list can also be accomplished using recursion by changing the links between nodes in a top-down manner. The base case occurs when you reach the end of the list, which becomes the new head. During the unwinding phase of the recursion, you adjust the next pointers to reverse the list.

Key Points:
- Base Case: Recognize the end of the list or the sub-list to start reversal.
- Reversal Logic: Change the next pointers of nodes during the recursive call return phase.
- Head Update: The new head is the last node reached by the recursive calls.

Example:

public class Solution {
    public ListNode ReverseList(ListNode head) {
        // Base case: if head is null or only one node, it's reversed itself.
        if (head == null || head.next == null) return head;

        // Recursive call on the rest of the list.
        ListNode newHead = ReverseList(head.next);

        // Reverse the current node's pointer.
        head.next.next = head;
        head.next = null;

        // Return the new head of the reversed list.
        return newHead;
    }
}

3. How would you reverse a portion of a linked list from position m to n?

Answer: To reverse a portion of a linked list, you first navigate to the start position of the reversal (m), reverse the specified portion iteratively until position n, and then reconnect the reversed portion with the rest of the list. This involves careful pointer manipulation to ensure seamless connections.

Key Points:
- Navigation: Identify the start point (m) and end point (n) for reversal.
- Reversal: Reverse the nodes between m and n.
- Reconnection: Reconnect the reversed portion with the non-reversed parts.

Example:

public class Solution {
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;

        // Move the two pointers until they reach the proper starting point
        ListNode current = head, prev = null;
        while (m > 1) {
            prev = current;
            current = current.next;
            m--;
            n--;
        }

        // Conners to reconnect later
        ListNode connection = prev, tail = current;

        // Iteratively reverse the nodes until n becomes 0.
        ListNode temp = null;
        while (n > 0) {
            temp = current.next;
            current.next = prev;
            prev = current;
            current = temp;
            n--;
        }

        // Adjust the pointers to reconnect the reversed portion
        if (connection != null) {
            connection.next = prev;
        } else {
            head = prev;
        }

        tail.next = current;
        return head;
    }
}

4. Discuss the space and time complexity of your linked list reversal algorithm. Can it be optimized further?

Answer: The iterative and recursive approaches for reversing a linked list have different space and time complexities. The iterative method generally has a time complexity of O(n) and space complexity of O(1), as it processes each node once without using additional data structures. The recursive approach also has a time complexity of O(n) but a space complexity of O(n) due to the call stack used for recursion.

Key Points:
- Iterative Method: Time complexity is O(n), and space complexity is O(1).
- Recursive Method: Time complexity is O(n), but space complexity is O(n) due to recursion.
- Optimization: The iterative method is already optimized regarding space. For recursive, space optimization isn't straightforward due to the nature of recursive calls.

Example:

// Iterative approach is demonstrated in question 1, which is the optimized approach in terms of space.

The iterative approach is preferred for its space efficiency, especially in environments where stack size and memory usage are concerns.