We continue this process until a null child is reached - at which point we can return the most recent prev node which is our new head. We then iterate forward by pointing prev to the current node and curr to the original next node. Prev points to null (the head has no parent), curr points to the current node (the head), and, if there is indeed a current node, temp_next points to the current node's child.Īt each iteration, we assign the current node's next pointer to the node at prev (reversing the reference). The task of any iterative traversal is managing pointers across iterations.įirst, let's set up our state-of-the-world for the head (input) node. Reversing a linked list with an iterative approach is more space efficient than the recursive solution, and tends to be more easy to grasp. Space Complexity: O(n) Although we are not constructing a new linked list, recursion requires linear space on the call stack to maintain a reference to each execution context.Reverse Linked List Python and JavaScript Recursive Solutions We also set the current node's next pointer to null - this will be overwritten once the subsequent recursive call is resolved, except for the original head which is now the tail and therefore has no next node. As each context is popped off the stack, we assign the current node's child's next pointer to the current node, effectively reversing its reference. Once a null node is reached (our base case), we begin the reassignment process.
#Reverse a linked list update
Why "post-order"? The key here is to recurse on each subsequent node until the last node is reached, and then update the next pointers as each execution pops off the call stack.Įach call to the recursive function reverse_list is passed in a reference to the current node's child, which adds a new execution frame to the call stack. Let’s consider a post-order recursive traversal to reverse the list. Since a linked list is an inherently recursive data structure, it makes sense that we can employ a recursive approach. A linked list can be traversed both recursively and iteratively - in both approaches, we maintain a reference to the current node, its parent, and its child, and re-assign the next reference for each node. Let's explore how we can update each linked list node in-place with a linear traversal. Since we'll need to visit each node at least once, our solution space is limited to a linear traversal. We can imagine a null node at the head and the tail of the list.Īt minimum, reversing a given linked list will require updating each node's next pointer to reference its parent. And while there is no node pointing to n1, we can imagine that its parent is null. But what would n1 point to? Recall that while n2 does not have a child because it is at the end of the list, the node's next property still exists - it simply points to null. If this list were to be reversed, its clear that n2 would point to n1. In this original linked list, the first node ( n1) points to the second node ( n2) with the next property. Here's an example of a linked list with two listnodes: class Node: For a doubly linked list, we would also have a prev property that points to the previous node on the list. Instead, for a singly linked list we're given a head node with a next property that points to the subsequent node in the list. Unlike an array, a linked list is a recursive data structure - each node points to another node - which means we don't have random access to its members.
After all, this interview question is an opportunity to demonstrate your familiarity with the data structure. This will be the new first node.Before we can reverse a linked list, let’s start our approach with a concrete understanding of how a singly linked list works. Here, assuming a simple Node class with next-pointer: /**
#Reverse a linked list Patch
I thought about a solution which would work for a singly-linked list (but not for something like ArrayList), but sadly the ListIterators add method inserts the element before the cursor instead of after it, thus it is not doable with the List + ListIterator interfaces (if we can't patch the ListIterator implementation to cache the pre-insert element to allow a single previous() after add in O(1)). It should work for both LinkedList and ArrayList. If you have constant-time next() and previous() for the iterators, use the solution already given. As discussed, in the general case this is not doable, you need to assume something about the complexity of the individual operations.
0 kommentar(er)
