52. Linked-List-4: (Two singly LL problems)

  • Add 2 LL✅🔥
  • Poi of 2 LL✅
  • merge 2 sorted LL✅
  • merge K sorted LL✅
  • sort LL🔥
    ---------------------------------------------------------------------------------------------------------------
    1. Add 2 LL

    use concept of Dummy node to create a new LL while traversing given 2 LLs


    ---------------------------------------------------------------------------------------------------------------
    2. Poi of 2 LL

    Brute force- 
    traverse one LL and hash the nodes & when u traverse the other LL, the first visited node u visit is ans


    --------------------------------------------------
    Better-
    instead of using extra space, we will move ptr of Longer LL till it reaches starting posn of shorter LL, and then we start simultaneous traversal of both

    ---------------------------------------------------
    Optimal-

    1. move both ptrs starting from respective heads
    2. whenver a ptr reaches last node, move that ptr to head of other linked list & move other ptr as usual
    3. now keep moving the ptrs & if u see step 2 situation then do above stuff & repeat

    aise karte karte at one time, both ptrs will be vertically aligned, so then they would simultaneously reach common poi

    ---------------------------------------------------------------------------------------------------------------------------

    3. merge 2 sorted LL

    Brute - store all elements and then sort them and convert this array into a LL

    Optimal- (time: O(n1+n2) )

    use 2 pointers across 2 LL conditionally and add smaller element to LL
    instead of creating a new LL, just use one dummy node & start connection

    ---------------------------------------------------------------------------------------------------------------------------

    4. merge K sorted LL

    Brute-
    use array & sort array & then convert array to a new LL

    Better- (time ~ N*k*k)
    we will do a repeated merge 2 sorted LL, like first merge list 1 & 2 and then merge this new list with list 3 & so on

    Optimal-(time- N*K*logK)
    use min-heap
    1. store all heads in a priority queue in form of pairs as ( val, node)
    2. create a dummy node
    3. add min out of pq to dummy->next and add pop wale node ka next into pq
    4. repeat step 3


    ----------------------------------------------------------------------------------------------------------------------------

    5. sort a LL

    Brute- O(n) space
    simple, store all elements in a data structure--> sort them-->over write the LL

    Optimal- (merge sort): O(1) space

    1. divide the list into 2 lists and repeat the process till, we get single nodes
    2. now sort them and merge using merge 2 sorted LL algo
    3. repeat


    merge sort in arrays-

    merge sort in LL-
    1. find middle using tortoise hare algo
    2. left LL start from head & right LL start from middle-->next
    3. separate the 2 LL and call merge sort again recursively for these 2 LL to get 2 sorted LL
    4. merge these 2 sorted LL

    Edge case-
    Tortoise hair algo returns second middle in case of even length LL, we want first middle in even length LL for split, so modify that algo
    so we will start fast from (head--->next) instead of head 

    --------------------------------------------------------------------------------------------------------------

    Comments

    Post a Comment

    Popular posts from this blog

    18. greedy algorithm

    Image
    assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
    Read more

    19. strings (LB)

    Image
    strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
    Read more

    17. BINARY SEARCH on 2d arrrays

    Image
     1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
    Read more