Prompt
Given the head of a singly linked list, reverse the list, and return the reversed list.
Examples
- Example 1:
- Input: head = [1,2,3,4,5]
- Output: [5,4,3,2,1]
- Example 2:
- Input: head = [1,2]
- Output: [2,1]
- Example 3:
- Input: head = []
- Output: []
Solution
In C++
ListNode * reverseList(ListNode * head) {
if (!head) return nullptr;
ListNode * prev = nullptr;
ListNode * curr = head;
while (curr) {
ListNode * next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}Explanation
I trace out how I would manually approach the problem:
N 1 -> 2 -> 3 -> N
p^c^
N 1 -> 2 -> 3 -> N
p^c^ t^
N <- 1 2 -> 3 -> N
p^ c^t^
N <- 1 2 -> 3 -> N
p^c^
N <- 1 2 -> 3 -> N
p^c^ t^
N <- 1 <- 2 3 -> N
p^ c^ t^
N <- 1 <- 2 3 -> N
p^ c^
N <- 1 <- 2 3 -> N
p^ c^ t^
N <- 1 <- 2 <- 3 N
p^ c^ t^
N <- 1 <- 2 <- 3 N
p^ c^
Essentially, you iterate throught the Linked List, and assigned the current node’s next node to the node before it. Once the current node is null, i.e. you’ve gotten to the end of the list, you’re done.
Big O Analysis
Time Complexity