![]() ![]() Think about what “flipping the arrows” would mean and make sure you keep track of any temporary variables you might need to hang onto while “flipping” through the list. ![]() You just gotta go through and flip the direction of all the yellow and blue arrows (and flip the green and red arrows to point to their counterpart). ![]() Imagine it were a line of beans with arrows pointing from one bean to the next (in yellow) and previous (in blue) with a special green arrow pointing to the first bean and a special red arrow pointing to the last bean. You need one or two temporary variables max, but nothing more. Reversing a doubly linked list is quite straightforward so there is no need whatsoever to leverage an array like this. Traverse the list from the head node again and pop a value from the stack top and connect them in reverse order. Algorithm : Traverse the list and push all of its nodes onto a stack. It works, but I would never hire someone who could not do better. Examples: Input : List 3 -> 2 -> 1 Output : 1 -> 2 -> 3 Input : 9 -> 7 -> 4 -> 2 Output : 2 -> 4 -> 7 -> 9. Since recursive implementation can run out of memory, the recursive solution isn't the best approach when working with very large linked lists. Each recursive call requires your compiler to allocate stack memory. This is the question's description: Given the head of a singly linked list and two integers left and right where left < right, reverse the nodes of the list from position left to position right, and return the reversed list. If I saw that answer in an interview I would be disappointed because you needed to create an auxiliary data structure that was a complete copy of all of the data in your existing data structure you were operating on (so any time that method is called it allocates O(n) space). Solution 2: Reverse a linked list using recursion. Linked List is a data structure consisting of a group of vertices (nodes) which together represent a sequence. I was working on Stack Overflow and came up across the 92. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |