Reverse Linked List

In the realm of linked lists, the task at hand is to reverse the entire structure efficiently. Picture this: you're given a linked list, and your mission is to flip it around completely. Let's delve into an algorithmic solution that achieves just that.

Example 1:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

The Approach

Our strategy involves the use of three pointers to keep track of the nodes while updating them.

1. Initialization:

• Initialize three pointers: current, prev, and next.
• current starts at the head of the linked list, and both prev and next are initially set to NULL.

This approach effectively iterates through the linked list, reversing the direction of the links between nodes. The prev pointer plays a crucial role in maintaining the reversed portion of the list as the algorithm progresses. This process continues until the entire linked list is reversed.

Let's walk through the solution using C++ code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* reverseList(ListNode* head) {
    ListNode* current = head;
    ListNode *prev = NULL, *next = NULL;
    while (current != NULL){
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
    }
    head = prev;
    return head;
  }
};

• Time Complexity: O(N), Traversing over the linked list of size N. 
• Auxiliary Space: O(1)