• 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

Find if a binary tree is height balanced ?

Connect n ropes with minimum cost

Python Array String

Longest Increasing Subsequence

Level order traversal in Spiral form

Count number of ways to reach a given score in a game

Templates in C++

Count Possible Decodings of a given Digit Sequence

Spanning Tree

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

25 horses 5 tracks Find 3 fastest puzzle

Amazon Interview Experience – SDE Chennai

Microsoft BING Interview Experience

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

Stickler thief

Python List

BFS (Breath First Search)

Print Power Set of a Set

Common Ancestor in a Binary Tree or Binary Search Tree

LeetCode : Word Search

Subset Sum Problem Dynamic programming

Find if two rectangles overlap

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Linked List V/S Binary Search Tree

Implement a generic binary search algorithm for Integer Double String etc

Daughter’s Age VeryGood Puzzle

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

Word Break Problem

VMWare SDEII Interview

Copyright © 2025 · Genesis Framework · WordPress · Log in