Introduction

Reversing a singly linked list is a classic algorithmic problem often encountered in technical interviews and computer science courses. A singly linked list is a data structure made of nodes where each node consists of data and a reference (link) to the next node in the list. Reversing such a list involves changing the direction of pointers so that the last node becomes the head and the head becomes the last node. Typically, three pointers are used to achieve this, but it is possible to reverse a singly linked list using only two pointers. In this article, we explore how to accomplish this and dive into the technical details.

Understanding Singly Linked Lists

Before diving into the reversal process, it is essential to understand the basic structure of a singly linked list:

• Node: A basic unit of a linked list consisting of data and a reference to the next node.
• Head: The first node in the linked list.
• Tail: The last node in the list, which points to NULL.

Example of a Singly Linked List

[Head] -> [2] -> [3] -> [4] -> [5] -> [NULL]

Reversing the Linked List Using Two Pointers

In the conventional method of reversing a linked list, three pointers—previous, current, and next—are typically used. Here, we focus on a more elegant technique that uses only two pointers.

Algorithm Explanation

1. Initialize Pointers: Begin by initializing two pointers:
   • prev as NULL (since the new tail’s next should be NULL).
   • current pointing to the head of the list.
2. Iterate through the List: Use a loop to traverse through the list until the current pointer becomes NULL.
3. Reversal Process:
   • In each iteration, memorize the next node by storing current->next in a temporary variable temp.
   • Reverse the next reference of the current node to point to prev.
   • Move the prev and current pointers one step forward (prev becomes current and current becomes temp).
4. Update the Head: Once current is NULL, the prev pointer will be positioned at the new head of the reversed list.

Detailed Code Example

Here is a C-style pseudo-code illustrating the two-pointer method:

1Node* reverseListUsingTwoPointers(Node* head) {
2    Node* prev = NULL;
3    Node* current = head;
4
5    while (current != NULL) {
6        Node* temp = current->next; // Store next node
7        current->next = prev;       // Reverse current's pointer
8        prev = current;             // Move pointers one step forward
9        current = temp;
10    }
11    head = prev;  // Update head to the new front of the list
12    return head;
13}

Key Pointers and Steps

The table below summarizes the key pointers and steps in the reversal process:

Complexity Analysis

Time Complexity

The time complexity of this algorithm is $O(n)$, where $n$ is the number of nodes in the linked list. This is due to the single pass through the list in the while loop.

Space Complexity

The space complexity is $O(1)$ because we only use a constant amount of extra space, merely two pointers and a temporary variable.

Conclusion

Reversing a singly linked list is a fundamental but crucial operation, and understanding how to do so with only two pointers provides elegant insight into the mechanics of pointer manipulation. This approach minimizes auxiliary storage while maintaining simplicity and efficiency. Mastering these fundamental concepts is invaluable for anyone interested in algorithms or data structures.

By focusing exclusively on two pointers, this method captures the essence of in-place algorithm design and emphasizes the power of thoughtful data manipulation in reducing complexity.