• 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

Print Power Set of a Set

Find loop in Singly linked list

Best Java Book | Top Java Programming Book for Beginners

Find min element in Sorted Rotated Array (Without Duplicates)

ADOBE Aptitude C Language Test

Find and print longest consecutive number sequence in a given sequence in O(n)

Python Array String

Maximum path sum between two leaves

Maximum occurred Smallest integer in n ranges

Count Possible Decodings of a given Digit Sequence

Cisco Hiring Event 21st – 22nd Feb 2015

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

System Design: Designing a LLD for Hotel Booking

Trapping Rain Water

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Stock Buy Sell to Maximize Profit

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

Password Predictor

SAP Interview Questions

Right view of Binary tree

CodeChef’ RRCOPY

Linked List V/S Binary Search Tree

Reliance Jio Software Developer Interview Experience

Reversal of LinkedList

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

Given a string, find the first character which is non-repetitive

Get Minimum element in O(1) from input numbers or Stack

Hackerearth : Counting Subarrays

Max Sum in circularly situated Values

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

Copyright © 2023 · Genesis Framework · WordPress · Log in