Problem
Given the head of a singly linked list, reverse the list and return the new head. The links between the nodes must be reversed without creating a separate linked list.Example(s)
Consider the following example(s) to understand the expected input and output.Input
head = [1,2,3,4,5] Output
[5,4,3,2,1] Solution
This solution uses three pointers: prev, current, and next. The prev pointer stores the previously processed node, while current points to the node currently being processed.For each node, the next node is temporarily stored so that the remaining list is not lost. The next pointer of the current node is then reversed to point to prev.
Finally, both pointers are moved forward and the process continues until all nodes have been processed. After the traversal, prev points to the new head of the reversed list.
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
Complexity
The algorithm traverses every node exactly once, resulting in a time complexity ofO(n). The list is reversed in-place using only a few pointers, so the extra space complexity is O(1).