Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
The description was taken from https://leetcode.com/problems/reverse-linked-list/.
#Iterative#O(N) Time, O(1) Spaceclass Solution:
def reverseList(self, head: ListNode) -> ListNode:
previous, current = None, head
while current:
bridge = current.next
current.next = previous
previous = current
current = bridge
return previous#Recursive#O(N) Time, O(N) Spaceclass Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_headWe can solve this question by iterating through the linked list and setting each next node reference as the previous node, thus reversing the list. What is important here is to cache the current node's next pointer before setting the reference to the previous node so that the next node can be traveled to after its reference has been overwritten by the previous node.
We will do this by utilizing three pointers. Our previous pointer will be used to track the previous node, current will be used to track the current node, and bridge will be used to track the next node.
We will initialize our previous and current nodes at none and the head, respectively.
Think about it, once we overwrite the head's next reference to none, we have successfully created the new tail of the list, since the tail points to none.
previous, current = None, head
While the current pointer isn't at a null node, we continue moving down the list, setting each current pointer's next reference to the previous node.
while current:
At the beginning of each iteration, we will save bridge as the next node.
bridge = current.next
We want to do this because once we overwrite current.next and set it to the previous node, we will lose our bridge to get to the next node.
Once we saved our bridge, we will overwrite the reference to our next node by setting it to the previous node, previous.
current.next = previous
We will then move our previous pointer to the current pointer, and our current pointer will cross the bridge to the next node.
previous = current
current = bridge
The traversal through the list will basically look like us grabbing each current pointer's next node, attaching it to the node behind us, and hopping the bridge to the next node.
Once we have traversed the entire list and reversed each pointer, we will return the previous pointer because the loop broke when the current node reached a null value, so if we were to return it then we would return nothing.
The previous pointer will have stopped at the old tail, which is now the new head.
return previousThe recursive solution is quite straightforward compared to the iterative solution.
We don't need to keep track of the previous and next nodes because they are kept in the call stack.
All we need to do here is run a recursive Depth-First Seach to find the current tail node, set that tail node as the new head, and set its next pointer to the last function call's current head, and the current head's next pointer to null.
In the iterative version, we were setting each current node to the previous node, in this version, we are setting each next node to the current node then setting the current node's next value to none so that we pass the tail from the very end of the list to the very right within each recursive call.
Once all of the recursive calls have been satisfied, the initial list will be reversed.
Being a recursive function, we will need to make sure we set our base cases first.
If the head is None then have nothing to return, so we will just return the head which would be None.
If head.next is None, then we are at the tail of the input list. Remember, the last node of the input list points at None. If this happens, we will return the head, this is the node we were looking for in our DFS.
if not head or not head.next: return head
We will perform our DFS right off the bat.
The initial function call and all of the child calls won't reorder any pointers until we have gone deep enough within the linked list to find the tail node which is the new head.
Once that happens, we will set the new head as what was returned from that recursive call.
new_head = self.reverseList(head.next)
Once a current function call has gotten a node passed up from its recursive call, we will set the current call's head's next reference to the current head.
Remember, the first time this happens the head's next, next reference will be pointing at None and each time thereafter.
head.next.next = head
After we have set the next node's value to the current node, we will set the current node's next value to None.
Remember, the last time this happens on the very top-level of the recursive tree, the old head will be pointing to None because it is the new tail.
head.next = None
Once the list has been reversed, we will return the new list starting from the new head.
return new_head
Let's walk through a quick example to illustrate how this recursive version works.
We'll use the input of [1,2,3,4].
1->2->3->4->None
The head is one.
The base case isn't met, recurse the function to get the new head.
1->2->3->4->None
The head is two.
The base case isn't met, recurse the function to get the new head.
1->2->3->4->None
The head is three.
The base case isn't met, recurse the function to get the new head.
1->2->3->4->None
The head is four.
The base case is met, head.next is None. We found the new head, return it!
1->2->3->4->None
The head is three.
1->2->3->4->None
Move head's next, next value to head. Move head's next value to None and return new_head.
1->2->3->None<-3<-4
The head is two.
1->2->3->None<-3<-4
Move head's next, next value to head. Move head's next value to None and return new_head.
1->2->None<-2<-3<-4
Finally, the head is one.
1->2->None<-2<-3<-4
Move head's next, next value to head. Move head's next value to None and return new_head.
None<-1<-2<-3<-4
We're done!
4->3->2->1->None