Given a singly linked list we want to reverse it.
Example:
1,2,3,4,5
Ans. 5,4,3,2,1
Solution
We can solve this problem with three pointers approach
We need Original Head, NewHead and NewNode pointers.
Steps
- We will create a Newhead pointing to null
- We will iterate through the linked list one node at a time and do the following steps
- We create a new node with value from Original Head. So in the first iteration we will have one Node with value 1
- We will assign the next of the NewNode to New head. So in the first iteration we will have one node 1 pointing to Null as new head is null and hence we make it the end node
- update newHead where Newnode is so that in the next iteration newnode next will be assigned newHead at step 2
static SinglyLinkedListNode ReverseLinkedList(SinglyLinkedListNode origHead)
{
SinglyLinkedListNode newHead = null;
while (origHead != null) {
SinglyLinkedListNode newNode = new SinglyLinkedListNode(origHead.data);
newNode.next = newHead;
newHead = newNode;
origHead = origHead.next;
}
return newHead;
}
The space complexity of this algorithm is O(n). We can do better with just reversing the pointers as follows
public ListNode ReverseListUsingTemp(ListNode head)
{
ListNode prev = null;
ListNode next = null;
ListNode curr = head;
while (curr != null) {
next = curr.next; // Save the next node
curr.next = prev; // Reverse the current node's pointer
prev = curr; // Move the previous pointer one step forward
curr = next; // Move the current pointer one step forward
}
return prev; // New head of the reversed linked list
}
}