![]() Time Complexity = O(n), where n is the length of the Linked List ListNode restReversedPart= reverseList(head.next) If(head = NULL || head.next = NULL) then return Null. Return the head pointer of the reversed list i.e. So, do the following operations to ensure this: Recursively reverse the linked list with (n-1) nodes and return the head pointer of this part i.e.īut for the complete reversal of the list, the head should be the last node. We can divide the linked list with n nodes into two parts: head and the rest of the linked list with n-1 nodes This idea can be implemented in two ways → We will follow the same approach for all the node and finally our new reversed Linked List will be ready. The idea here is to de-link a node from its previous node and add the previous node in front of the current node. ![]() What if only one node is given in input?( No, just return the head of the reversed Linked List.) Possible follow-up questions to ask the interviewer:ĭo we have to print the Linked List in reverse order?( This should be done by de-linking the nodes and again linking it in reverse order. After the reversal, The head data should become the last data element pointing to null. Given a linked list pointed by a head node as input, your task is to reverse the linked list. Asked in: Microsoft, MakeMyTrip, Adobe, Amazon new ( 62, node1 ) node3 = LinkedListNode. To put it all together and to complete the challenge of reversing the linked list do the following: node1 = LinkedListNode. Reversing the linked list after creating the stack was easy as I knew all I need to do was to traverse the linked list pushing each value onto the stack until the end of the linked list. pop # => nil Reverse the Linked List using a Stack We can use the stack like so: stack = Stack. Then when we pop from the stack it prints which is at the top of the stack and then it will set the stack to be the next_node thus removing the top LinkedListNode from the stack. What’s happening here is when a value is pushed onto the stack it will create a new LinkedListNode using the value, while the pointer will become what was previously, this could be nil or a previously pushed LinkedListNode. To output the contents of the linked list we can build a method that uses recursion to traverse the linked list like so: def print_values ( list_node ) if list_node print " # \n " =. Then we can build up a linked list by creating some nodes and linking them like so: node1 = LinkedListNode. ![]() Implementing a linked list in Ruby can be achieved like so: class LinkedListNode attr_accessor :value, :next_node def initialize ( value, next_node = nil ) = value = next_node end end There are more complex versions of linked lists such as doubly linked list, multiply linked list and circular linked list. The start or entry point of a linked list is called the head and last node will have a pointer of null. A data element, also known as a node, and a pointer element to the next node. Ruby Linked List Pt3 Floyd’s Cycle Detection What is a Linked ListĪ linked list is linear data structure that consisting of 2 elements. Ruby Linked List Pt2 Reverse using mutation The challenge was specially to create a stack class and then reverse the linked list using this stack. In this challenge I learned about 2 new data structures a linked list and a stack and how to implement them by hand. ![]()
0 Comments
Leave a Reply. |