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. Before we can reverse a linked list, let’s start our approach with a concrete understanding of how a singly linked list works.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |