Solution: Reverse a Linked List
Example:
The original linked list is as follows:
3 -> 5 -> 2 -> 4The reversed linked list has its arrows changed in direction:
3 <- 5 <- 2 <- 4which means
4 -> 2 -> 5 -> 3
Don’t create new nodes. Instead, reuse the original linked list, and modify the arrow directions in-place.
Input:
The linked list’s node values, separated by commas.
3 5 2 4
Output:
The reversed linked list’s node values, separated by commas.
4 2 5 3
Solution: Reverse a Linked List
Observe
A linked list can be split into the head node and the tail, which is also a linked list but headed by the second node.
Insights:
Treat the tail as a linked list, and reverse it by recursively calling the reverse function.
Then, the first node is appended to the reversed tail to construct the entire reversed linked list.
Algorithm
- Cover the edge cases of the null and single-element linked list.
- Get the second node from the original linked list, and recursively reverse the tail.
- Append the first node to the end of the reversed tail.
Code
/**
* class Node {
* val: number,
* next: Node,
* }
*//**
* @param {Node} head Head of the linked list.
* @return {Node} Head of the reversed linked list.
*/
function reverseLinkedList(head) {
if (head == null || head.next == null) {
return head;
} const secondNode = head.next;
const reversedTail = reverseLinkedList(secondNode);
secondNode.next = head;
head.next = null; return reversedTail;
}
Complexity Analysis
Let N be the length of the linked list.
We visit each node in the linked list once, so the overall complexity is O(N).