Leetcode 206. Reverse A Linked List

HAOYU LEI
HAOYU LEI
Sep 2, 2018 · 2 min read

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.next

But 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 = next

Where 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 = next

Ok, 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 previous

We 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 previous

Bravo!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade