• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

flattens 2 D linked list to a single sorted link list

March 27, 2014 by Dhaval Dave

Write a function flatten() which flattens this linked list with each node down sorted link list to a single link list with all the elements in sorted order.

We have given Two methods in O(n^2) here.
for different linked list.

5 -> 7 ->  9 -> 18
 |    |    |    |
10    8    14   20
 |    |    |    |
11    8.5  19   22
 |    |         |
12    13        24
 |    
15


Method 1 :
Keep Two pointers and print all elements and ie: 5,10,11,12,15,7,6,8,13 … and sort the array.
Time Complexity : O(n log n)

Method 2 :
We can Think to implement a method via which all numbers takes appropriate place in sorted order.

With Above Example.

1) Store first main list's element in Auxiliary Array 
Temp[]:  5 - 7 - 9 - 18. This Temp is sorted.

2) Take first Down elements and With the divide and conquer logic 
 place them at appropriate position.
 say 10.

- 10 > 5 , 10 <18
- divide in sub array {5,7},{9,18} 
- 10 < 5, 10 > 7 10 won't come in this array part.
- 10 > 9, 10 < 18 put 10 in between 
- Result set 5,7,9,10,18
3) Similarly do for all elements in fist down list

 after first down link list
 Result Set : 5,7,9,10,11,12,15,18.
 take second list elements
 say 8.

- 8 > 5 , 8 < 18
- divide {5,7,9,10} and {11,12,15,18} 
- 8 > 5 , 8 < 10 & 8 < 11 ,8 < 18 => 8 won't come in this array part
- divide {5,7} {9,10} 
- repeating same we can put 8 in after 5, 7 and
- Result set will be 5,7,8,10,11,12,15,18.. like wise complete all.


Time complexity O(n log n) where n is total number of elements

Method 3 : Use Merge sort  – Take one first two list with 5 and 7 as head node.
– Merge and sort them in any one auxiliary list say “Result”
– and continue with Result and other lists.
– eg.Take below trace of calls to understand code

1)merge(5,7)

2)if 5 < 7 : result = 5;
  result->down = merge (10,7)
  //in next call it will return 7.
  // so result list will be 5-7.
 
3) if 10<7 : X
   result = 7
   result->down = merge (8,10);
 // hence result will be 5-7-8 in next call .
In next steps result will continue like this and produce sorted flatten Linked List

Code : 

Node* merge( Node* a, Node* b )
{
    // If first list is empty, the second list is result
    if (a == NULL)
        return b;
 
    // If second list is empty, the first list is result
    if (b == NULL)
        return a;
 
    // Compare the data members of head nodes of both lists
    // and put the smaller one in result
    Node* result;
    if( a->data < b->data )
    {
        result = a;
        result->down = merge( a->down, b );
    }
    else
    {
        result = b;
        result->down = merge( a, b->down );
    }
 
    return result;
}
 
// The main function that flattens a given linked list
Node* flatten (Node* root)
{
    // Base cases
    if ( root == NULL || root->right == NULL )
        return root;
 
    // Merge this list with the list on right side
    return merge( root, flatten(root->right) );
   
}

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Microsoft Interview Questions, problem Tagged With: Linked List, Merge Sort

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Maximum of all subarrays of size k

Printing intermediate Integers between one element & next element of array

C Program for TAIL command of UNIX

Check if an array has duplicate numbers in O(n) time and O(1) space

Given a float number convert it into the string WITHOUT using any inbuilt Function

Amazon Interview On-Campus For Internship – 1

How strtok() Works

Fibonacci Hashing & Fastest Hashtable

Singly linked list

K’th Largest Element in BST when modification to BST is not allowed

Client Server C program

Cisco Hiring Event 21st – 22nd Feb 2015

Password Predictor

Edit Distance ( Dynamic Programming )

Reverse a Linked List in groups of given size

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Leetcode: Merge Intervals

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Right view of Binary tree

Coin Collection Dynamic Programming

Knight Tour Problem (Graph – Breadth First Search)

Microsoft BING Interview Experience

Linked List V/S Binary Search Tree

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Print vertical sum of all the axis in the given binary tree

Sort an array according to the order defined by another array

Binary Tree Isomorphic to each other

Amazon Interview Experience – SDE Chennai

Copyright © 2025 · Genesis Framework · WordPress · Log in