Reverse a Singly Linked List

51.9k
0

Given the head of a singly linked list, reverse the linked list and return the new head.

Example 1

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

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

Explanation: Pointer direction changes across every adjacent pair, so traversal from the new head gives values in reverse order.

Example 2

Input: head = [1, 2]

Output: [2, 1]

Explanation: The second node becomes the new head, followed by the first node.

Brute Force Approach

The linked list is traversed from head to tail while storing the value of every node in a stack. Since a stack follows the Last In, First Out (LIFO) principle, popping the values retrieves them in reverse order.

After collecting all values, we traverse the linked list again. During this traversal, we repeatedly pop values from the stack and overwrite the current node's value. This reverses the values stored in the linked list while keeping the node connections unchanged.

Algorithm

  • Create an empty stack to store the values of the linked-list nodes, as the stack's LIFO property will naturally provide the values in reverse order.

  • Traverse the linked list from head to tail and push every node's value onto the stack, so the last node's value becomes the first value available for reconstruction.

  • Reset the traversal pointer to head, since the same nodes will be reused while only their values are being changed.

  • Traverse the linked list again from head to tail, as each node now needs to receive its corresponding reversed value.

  • Pop the top value from the stack and assign it to the current node, since the most recently stored value belongs at the current position.

  • Continue this process until all nodes have been updated, resulting in the values being reversed while the linked-list connections remain unchanged.

  • Return the original head, as the node structure has not been modified and only the values have been rearranged.

Dry Run

Reverse linkedlist using stack

Reverse linkedlist using stack

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int data) { val = data; next = nullptr; }
};
class Solution {
public:
// Function to reverse linked list values using a stack.
ListNode* reverseList(ListNode* head) {
stack<int> values;
ListNode* current = head;
// Store all node values in LIFO order.
while (current != nullptr) {
values.push(current->val);
current = current->next;
}
current = head;
// Replace node values using stack top values.
while (current != nullptr) {
current->val = values.top();
values.pop();
current = current->next;
}
return head;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->val;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
ListNode* head = createList(arr);
Solution sol;
head = sol.reverseList(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N), two complete traversals over the linked list.

Space Complexity: O(N), stack stores all node values.

Optimal Approach

Instead of reversing the values stored in the nodes, we reverse the links between the nodes. We maintain three pointers: prev, current, and front (or next). Before changing a node's next pointer, we save the address of the next node so that the remaining list is not lost.

At each step, we reverse the current node's link, then move all three pointers one step forward. Once all nodes have been processed, the last processed node becomes the new head of the reversed linked list.

Algorithm

  • Initialize prev as NULL and current as head, where prev represents the already reversed part and current represents the node currently being processed.

  • Traverse the linked list while current is not NULL, as every node's link needs to be reversed.

  • Store current->next in a temporary pointer front, since changing current->next before saving it would lose access to the remaining part of the list.

  • Update current->next to prev, which reverses the link of the current node and connects it to the already processed portion.

  • Move prev to current and current to front, as the reversed portion now includes the current node and the traversal needs to continue with the saved next node.

  • Continue until current becomes NULL, which signifies that every node has been processed and prev is now pointing to the last node of the original list.

  • Return prev as the new head, since it represents the beginning of the completely reversed linked list.

Dry Run

optimal dry run

optimal dry run

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int data) { val = data; next = nullptr; }
};
class Solution {
public:
// Function to reverse a linked list by changing links.
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
// Traverse nodes and reverse one link per step.
while (current != nullptr) {
ListNode* front = current->next;
current->next = prev;
prev = current;
current = front;
}
return prev;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->val;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
ListNode* head = createList(arr);
Solution sol;
head = sol.reverseList(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N), each node is visited exactly once.

Space Complexity: O(1), only constant extra pointers are used.

Interview follow-up Questions

Yes. The optimal approach changes next pointers using three pointer variables and uses constant extra space.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links inste...

59.8k
Linked List

Sort a Linked List Using Merge Sort

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list. Each node contains an integer value and a pointer to the next nod...

112.1k
Linked List

Find pairs with given sum in Doubly Linked List

Input: DLL = [1, 2, 4, 5, 6, 8], target = 7 Output: [[1, 6], [2, 5]] Explanation: Values 1 and 6 form sum 7. Values 2 and 5 also form sum 7. Input: DLL = [1, 3, 5, 7, 9], target = 10 Output: [[1, 9...

101.5k
Comments0