Leetcode 206. Reverse A Linked List
It is such a standard and classic problem that ignoring it would be too impolitic. I have a deep impression about it being the last question in final exam and I didn’t finish because I was running out of time. So it’s also worthy of a review.
The key here is to put everything aside first and identify it’s key operation: changing each node’s next pointer to point to it’s previous node, and then move to the next node. Let’s put down the pseudocode of the key operation first:
ALGORITHM reverseList(head)
current.next = previous
current = current.nextBut immediately we notice certain information is missing during the operation: current.next has already changed before we move on. Therefore, we need to allocate some space to keep the original current.next:
ALGORITHM reverseList(head)
next = current.next
current.next = previous
current = nextWhere is previous? It is the previous node of current node in the given linked list. Where can we set it in the code? Right before we move current pointer to the next node:
ALGORITHM reverseList(head)
next = current.next
current.next = previous
previous = current
current = nextOk, so this consists of the core body of our iterative solution. The rest are just conditions to terminate:
ALGORITHM reverseList(head)
current = head
while current != null do
next = current.next
current.next = previous
previous = current
current = next
return previousWe should also initialize previous to null, since the original head will become tail of the new linked list:
ALGORITHM reverseList(head)
current = head
previous = null
while current != null do
next = current.next
current.next = previous
previous = current
current = next
return previousBravo!