• 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

strtok()

Add Sub Multiply very large number stored as string

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Spanning Tree

Maximum difference between two elements s.t larger element appears after the smaller number

VMWare Openings

Flipkart SDET Interview Experience

Amazon Interview On-Campus For Internship – 1

Find min element in Sorted Rotated Array (Without Duplicates)

BFS (Breath First Search)

ADOBE Aptitude C Language Test

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

SAP Off Campus Hiring_ March 2015 Verbal Skills

System Design: Designing a LLD for Hotel Booking

Facebook Interview Question : Interleave List

Find Nearest Minimum number in left side in O(n)

The greedy coins game Dynamic Programming

Reverse a Linked List in groups of given size

1014 Practice Question of New GRE – Princeton

HackeEarth Flipkart’s Drone

Find the smallest window in a string containing all characters of another string

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Memory Efficient LinkedList

Generic Object Oriented Stack with Template

Leetcode: Merge Intervals

Practo Hiring Experience

Code Chef PRGIFT Solution

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

LeetCode: Binary Tree Maximum Path Sum

Closed Parentheses checker

Copyright © 2025 · Genesis Framework · WordPress · Log in