Reversing a linked list is a very common task in technical interviews. That’s why we devote a whole section of Interview Practice to them! Being able to solve this question easily is a great way to demonstrate to an interviewer that you’re a capable, competent programmer. Let’s discuss two different ways of reversing the direction of a linked list: recursively and iteratively.Linked list refresher
A linked list can be modeled by Node objects, where each node stores a value and a next pointer to the next node in the list. The last node in the list points to NULL, to indicate that you’ve reached the end of the list. You access the linked list by having access to a head pointer at the beginning of the list.
You need to apply a function reverse(head) that does two things:
- Reverses the direction of the arrows, changing the structure of the linked list, and
- Returns a pointer to the new beginning of the list.
So all the nodes will stay in place in memory, and only the direction of the pointers will change.
You probably wouldn’t implement a linked list this way in an actual program. There might be a lot of different references to the linked list before you reverse it.
If you call reverse(head1), you would update head1. But all the other pointers would then be stuck at the end of the linked list, and only head1 would be a good head pointer.
head1 was reversedTo get around this, you could make a LinkedList class, or a sentinel head that external references could point to that contains the pointer to the beginning of the linked list. Then you could safely update this reference without breaking any external references.
But so that we can focus on just the core algorithm, the solutions in this video use a simple version of the linked list.
Why is reversing a linked list tricky?
Linked lists are designed to be easy to traverse in the forward direction, and once a node passes a particular point there is no way of going back to it. If you were in a position where reversing order was something you needed to do often, then a linked list would be a poor choice of data structure and you’d be better off choosing something else.
So this isn’t a problem that you’d really ever encounter on the job. In technical interviews, though, this kind of question is asked as a way of assessing how well you can perform tricky manipulations. That’s why sometimes the problems that interviewers ask can feel kind of artificial.
In this video, I demonstrate two different approaches to reversing a linked list: a recursive one, and an iterative one.
The code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
def __init__(self, value, next = None): self.value = value self.next = None def reverseRecursively(head): # Recursive version # Base cases if head is None or head.next is None: return head new_head = reverseRecursively(head.next) # tailNode = head.next # tailNode.next = head head.next.next = head head.next = None def reverseIteratively(head): # Iterative version if head is None or head.next is None: return head # Setup alreadyReversed, current = head, head.next alreadyReversed.next = None while current is not None: storePtr = current.next current.next = alreadyReversed alreadyReversed = current current = storePtr return alreadyReversed |
