LinkedLists

Comparision between LinkedList, Array, Dynamic Array:

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

Parameter	LinkedList	Array	Dynamic Array
Indexing	O(n)	O(1)	O(1)
Insertion / Deletion at begning	O(1)		O(n)
Insertion / Deletion at ending	O(n)		O(n)
Insertion / Deletion in middle	O(n)		O(n)
Wasted Space	O(n)	0	O(n)

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

LinkedList Important Questions :

--------------------------------------------------------------------------------------------------------------------------------------------------
Q1. Implement stack using LinkedList?
Sol: create a LinkedList. make a push() function to insert elements at last, make a pop() function to delete elements from last.
--------------------------------------------------------------------------------------------------------------------------------------------------
Q2. Find nth node from the end of the LinkedList?
Sol: Take two pointers, initially both pointing to head, move them one node at a time. Start moving second pointer after first pointer reaches nth node. So when first pointer reaches last node the second will be on nth node from the last.
--------------------------------------------------------------------------------------------------------------------------------------------------
Q3. Check whether the given LinkedList is Null terminated or ends in a Cycle?
Sol: Take two pointers slow and fast. Make them point to head. Move slow one node at a time and fast by two node at a time. If they meet at any point then the list is having a cycle. Else fast node will terminate at some point.
--------------------------------------------------------------------------------------------------------------------------------------------------
Q4. Find the starting node where cycle starts in a LinkedList having cycle?
Sol: From the above solution, the node where fast and slow pointers meet, keep one of the pointer at that node and the other back to the head. Start moving them one node at a time, the node where they meet is the start of the loop.
--------------------------------------------------------------------------------------------------------------------------------------------------
Q5. Reverse a singly LinkedList?
Sol: We can take 3 pointers and reverse the LinkedList as below:

void Reverse() {
        LLNode curr=ll.first;
        ll.first=null;
        while(curr!=null) {
            LLNode temp=curr;
            curr=curr.next;
            temp.next=ll.first;
            ll.first=temp;
        }
        System.out.print("\nreverse: ");
        ll.disp();
}
--------------------------------------------------------------------------------------------------------------------------------------------------
Q6. Find the middle of the LinkedList?
Sol: Take two pointers slow and fast, initially both pointing to head. move slow one node at a time and fast two nodes at a time. When fast will point the last node the slow will be pointing the middle node.
--------------------------------------------------------------------------------------------------------------------------------------------------
Q7. Displaying the LinkedList From the end?
Sol:  Using recursion. time complexity: O(n),  space complexity: O(n)

void PrintListFromEnd(LLNode node) {
       if(!node) return;
      PrintListFromEnd(node.next);
      System.out.println(head.data);
}
--------------------------------------------------------------------------------------------------------------------------------------------------
Q8. Check if LinkedList is a palindrome?
Sol:
--------------------------------------------------------------------------------------------------------------------------------------------------
Q9. Swapping adjacent nodes in LinkedList?
Sol:
--------------------------------------------------------------------------------------------------------------------------------------------------
Q10. Merge two sorted LinkedLists in a single sorted LinkedList?
Sol:
--------------------------------------------------------------------------------------------------------------------------------------------------