Problem
Given the head of a singly linked list, reverse the list and return the new head.
Example
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]Solution
Iterative: walk the list, flipping each node’s next pointer to point backward.
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prevfunction reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Three pointers: prev, current, next. Save next, flip current’s pointer to prev, advance prev and current. Repeat until done.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?