26. Linked List-3 : (1 singly LL Problems)

 Medium Problems LL-

  • find middle node✅                            (2 pointer/ tortoise hare)
  • delete middle node✅
  • delete nth node from back✅
  • detect a loop✅                                    (hashing/ tortoise hare)
  • length of loop✅                                  (hashing/ tortoise hare)
  • find starting point of loop✅🔥          (hashing/ tortoise hare)

    • reverse LL✅                                        (stack, 2 pointer, recursion)
    • check palindrome✅                             (stack, half reversal)
    • add 1 to number represented by LL✅ (stack, reversal, recursion)

    • segregate odd even numbered nodes✅(Link Changing)
    • sort LL of 0s, 1s, 2s✅                          (Link Changing)

      -----------------------------------------------------------------------------------------------------------------------------Note:-
      Whenver u want new LL , use concept of dummy node
      dummy node mein desired nodes jodte jao aur end mein dummy ke aage se bani hui poori new linked list dedo
      ----------------------------------------------------------------------------------------------------------------------------

      1. finding Middle of  LL-

      Brute- O(n): length find krke middle elmt ki posn calculate krlo & then traverse krlo us tak...

      Optimal O(n/2):  ( Tortoise-Hare approach )

      use 2 pointers for traversal- fast pointer moves by 2 steps & slow pointer by 1 step
      when fast ptr reaches end of LL, at the same time slow ptr can be found at middle element

      write while loop condition as per fast being last or 2nd last node

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

      2. deleting Middle of  LL-

      find middle wale code mein slow ke piche ek prev ptr lagado

      -------------------------------------------------------------------------------------------------------------------------
      3. Del nth node from back-

      Let, list has L nodes:

        Brute: nth node from back means (L-n+1) th node from front so ques reduces to del kth node

        Optimal-

        • When fast is n nodes ahead, & both move together
        • After L-n steps, fast reaches the last node
        • And slow is at position ( L-n ) exactly before the nth node from end.

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

        4. Reverse LL-

        Brute-
        store elmts in a stack and then replace nodes of LL with elmts from stack 

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

        Optimal-1:  (iterative)
        we will use 3 pointers- prev, curr, next

        ---------------------------------------------------------------------------
        Optimal-2:  (recursive)
        we will leave reversal of n-1 nodes on recursion and just reverse 1st node as per other n-1 reversed nodes



        ----------------------------------------------------------------------------------------------------------------------------
        5. Palindrome LL check-
        Brute-
        use stack
        ---------------------------------------------------------
        Optimal-  reverse only 2nd half of LL & check Palindrome⭐
        1. find middle
        2. reverse the 2nd half of linked list (starting from slow->next)
        3. traverse in both halfs using first & second ptrs & check palindrome
        4. before returning true/ false, u must again reverse the 2nd half to original configuration

        for reversing 2nd half of LL to initialize slow ptr:
        in odd length LL stop fast ptr at last node
        in even length LL, stop at 2nd last node



























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

        6. Add 1 to number represented by LL-

        Brute force-
        use a stack
        ------------------------------------------------------
        Better-
        reverse LL

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

        instead of reversing we will use recursion to move back

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

        7. segregate odd & even numbered nodes


        Brute force-
        we can use a vector to store odd and then even numbered nodes and then over write the actual nodes using this list

        Optimal-

        without using extra space-
        1. we will connect all odd nodes
        2. we will connect all even nodes
        3. we will connect last odd node to first even node

        at last, even will always be ahead of odd & even will be at last node of LL
        so now, connect odd end to even start, which we stored in an extra ptr at start

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

        8. Sort LL of 0s, 1s, 2s-

        Brute- time: O(2n)
        count no. of 0s, 1s and 2s and over write the LL

        Optimal- time: O(n)
        Link changing by connect all 0s separately then all 1s separately then all 2s separately then connect end of 0s to start of 1s and end of 1s to start of 2s


        also delete all dummy heads at last to free up space
        --------------------------------------------------------------------------------------------------------------------------
        9. detect a loop-

        Brute Force-
        use hashing 

        Optimal-  (use tortoise and hare algo)

        a time will come when both will meet


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

        10. length of loop-

        Brute- 
        use hashing to count no. of nodes visited
        ------------------------------------------------------------
        Optimal-
        Tortoise hare algo se pehle toh detect loop wale code se slow fast ko match karake loop ke andar kisi ek node pe laao, ab kyuki loop ke andar hi ghumta rahega vo toh fast wale ko ek ek badhake count krte rho jab tak vo slow ko na mil jaye toh loop ke total nodes count ho jayenge-

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

        11. starting pt of loop-

        Brute-
        use hashing

        Optimal-🔥🔥🔥
        use tortoise hare algo
        1. detect loop wale code se collision point pe fast ptr ko le jao
        2. ab slow ptr ko LL ke start pe le jaake , slow aur fast ko 1 se aage badhate rho
        3. the node at which they collide is start of loop


        --------------------------------------------------------------
        Intuition-



        as per relative velocity, fast covers 'd' dist & slow covers 0 dist 
        or, we can also say, fast covers '2d' distance & slow covers 'd' dist
        at each step, distance 'd' between them reduces by 1


        we can also say dist between slow/ start of loop to collision point is 'd'
        so dist between collision point and starting point of loop is L1
        so they will collide in this problem since both covers L1 distance
        ---------------------------------------------------------------------------------------------------------------------------

        Comments

        Post a Comment

        Popular posts from this blog

        30.) DP on subsequences

        Image
        Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
        Read more

        19. Strings (LB)

        Image
        Character Array- 1. We use  1d character array  to simulate strings, e.g., char ch[10]; cin>>ch; 2. string ends with '\0' 3. cin with string works only if till space, tab or new line is absent in input... 4. work with character array just like a normal array, here only datatype is changed to char, else wise it is just an array -------------------------------------------- 5. In-Built functions- - int n = strlen(ch)   - strcmp(s1,s2)            // gives 0 if both strings are equal  - strcpy(dest,source)   // copies a string from dest to source -------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- It is a C++ STL 1. has dynamic size (can dynamically increase size when needed) 2. null terminator (\0) NOT required 3. Has built-in functions : - return s.size() - return s == "hello" - return s + "wor...
        Read more

        32. Binary Trees-2 (bfs/dfs med problems)

        Image
        Medium problems- more imp---------------------- height            ✅ diameter        ✅ max path sum✅⭐ Height Balanced BT check✅ identical BT check✅ Symmetric BT check✅⭐ medium imp------------------- Zig Zag traversal✅ Boundary Traversal✅ Vertical order Traversal✅⭐ less imp---------------------------- Top view ✅⭐ Bottom view✅ Right/ Left view✅ ----------------------------------------------------------------------------------------------------------------------------- 1. Max Depth of BT- height(tree)  =    n(nodes) in longest path from top to bottom time-N          space-N ----------------------------------------------------------------------------------------------------------------------------- 2. Balanced BT check- it means for every   node:      [ H(left) - H(right) ] <=1 Brute-          time: O(n^2) -------------------------------------------...
        Read more