Reversing a Singly Linked List with Two Pointers: Algorithm Analysis and Implementation

Core Algorithm Principle

Reversing a singly linked list is a fundamental operation in data structures, with the key lying in efficiently adjusting the pointer directions between nodes. The two-pointer algorithm maintains two critical pointers—new_root (the head of the new list) and root (the current traversal node)—to incrementally construct the reversed list. Specifically, in each iteration, the algorithm saves the next node of the current node, sets the current node's next pointer to point to the new list head, updates the new list head to the current node, and then moves to the next node. This process ensures each node is visited only once, resulting in a time complexity of O(n), and with only two additional pointers used, the space complexity is O(1).

Detailed Code Implementation

The following C code demonstrates the complete implementation of the two-pointer reversal algorithm:

#include <stdio.h>

typedef struct Node {
  char data;
  struct Node* next;
} Node;

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}

In the reverse function, new_root is initialized to null, representing the start of the new list. The loop traverses the original list, each time setting the current node's next to point to new_root, achieving reversal. For example, for a list a->b->c->d, after execution, it becomes d->c->b->a. The print_list function in the code is used to verify the result, outputting the list contents before and after reversal.

Time Complexity Analysis

The time complexity of this algorithm is O(n), where n is the number of nodes in the list. Since each node must be accessed to modify pointers, this is the theoretical lower bound for reversal operations and cannot be further optimized. The space complexity is O(1), as only a fixed number of pointer variables are used, independent of the list size.

Comparison with Other Methods

Traditional three-pointer methods (as mentioned in the question) may lead to errors due to improper pointer management, such as retaining only one node in tests. The two-pointer algorithm avoids such issues by simplifying the logic while maintaining the same efficiency. The implementation in Answer 2 also uses two pointers but further reduces the variable count by reusing the first pointer, with its core idea consistent with the above code. In summary, the two-pointer method is the optimal solution for reversing a singly linked list, balancing code simplicity and performance.