Given a singly linked list with an additional "arbitrary" pointer at e

1.	Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?
Answer» A simple SOLUTION is to go through all nodes one by one, finding the node with the next bigger VALUE than the current node and changing the next pointer for each node. This solution has an O time complexity (n^2). An Efficient Solution takes O(nLogn) time to complete. The APPROACH is to use MERGE Sort for linked lists. Traverse input list and for each node, copy the next pointer to arbit pointer. Sort the linked list formed by arbit pointers USING Merge Sort. Here, all of the merge sort methods are altered to work with arbit pointers rather than the next pointers.

Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?

Answer»

A simple SOLUTION is to go through all nodes one by one, finding the node with the next bigger VALUE than the current node and changing the next pointer for each node. This solution has an O time complexity (n^2).

An Efficient Solution takes O(nLogn) time to complete. The APPROACH is to use MERGE Sort for linked lists.

Traverse input list and for each node, copy the next pointer to arbit pointer.
Sort the linked list formed by arbit pointers USING Merge Sort.

Here, all of the merge sort methods are altered to work with arbit pointers rather than the next pointers.

Discussion

No Comment Found

Related InterviewSolutions

Given a linked list with each node representing a linked list and two pointers of its type given below. You need to flatten the lists into a single linked list. The flattened linked list also needs to be sorted. Discuss the approach.
In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node?
Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?
Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space.
Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1).
Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?
Given two polynomial expressions represented by linked lists. You need to write a function that adds these lists, that is, adds the coefficients that have the same variable powers.
How will you find the length of a linked list which contains a cycle?

Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment