LinkedList.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------LINKED LIST-----------------------------------------
	


1. Reverse Linked List (both Iteratively and Recursively)

-> Iteratively
public void RPI() {
		Node prev = head;
		Node curr = head.next;
		Node ahead;
		while (curr != null) {
			ahead = curr.next;
			curr.next = prev;
			prev = curr;
			curr = ahead;
		}

		// head tail swap
		Node temp = head;
		head = tail;
		tail = temp;
		tail.next = null;
	}

-> if tail is not there

Best-1)

public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }else if(head.next==null){
            return head;
        }
        
        ListNode prev= head;
        ListNode curr=head.next;
        ListNode ahead;
        while(curr!=null){
            ahead=curr.next;
            curr.next=prev;
            prev=curr;
            curr=ahead;
        }
        ListNode temp=head;
        head=prev;
        prev=temp;
        prev.next=null;
        
    return  head;
    }

Best-2)

static Node reverse(Node head) {
        if (head == null || head.next == null) return head;

        Node tail = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }

-> Recursively
public void RPR() {
		RPR(head, head.next);
		Node temp = head;
		head = tail;
		tail = temp;
		tail.next = null;
	}
	private void RPR(Node prev, Node curr) {
		if (curr == null) {
			return;
		}

		// another method
//		Node ahead = curr.next;
//		curr.next = prev;
//		RPR(curr, ahead);

		RPR(curr, curr.next);
		curr.next = prev;
	}

-> Another Method

public ListNode reverseList(ListNode head) {
       if(head==null)
           return head;  
          ListNode p=solve(head);
           p.next=null;
        return glob;
    }
    static ListNode glob=null;
    
      
    public ListNode solve(ListNode node){
     if(node.next==null){
         glob=node;
         return node;
     }
        ListNode temp = solve(node.next);  
        temp.next=node;
        return node;
    } 

--------------------------------------------------------------------------------------------------------
2. Detect Loop in LinkedList.->https://www.youtube.com/watch?v=LUm2ABqAs1w
#Floyd cycle detection algorithm
public static boolean detectLoop(Node head){
        
        Node slow=head;
        Node fast=head;
        
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
             if(slow==fast)
             return true;
        }
        return false;
    }

--------------------------------------------------------------------------------------------------------
3. Find first node of loop in a linked list
 public ListNode detectCycle(ListNode head) {
       //works for one node
        if(head==null||head.next==null){
            return null;
        }  
        
        ListNode slow=head;
        ListNode fast=head;
        
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
             if(slow==fast)
                break;
        }
         if(slow!=fast){
             return null;
         }
            slow=head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
--------------------------------------------------------------------------------------------------------
4. Remove loop from LinkedList 
   public static void removeLoop(Node head){
         if (head == null || head.next == null)
            return;
        Node slow=head;
        Node fast=head;
        
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
             if(slow==fast)
                break;
        }
         //when first element is the starting of the loop
         if(slow==head){
             while(fast.next!=slow){
                 fast=fast.next;
             }
             fast.next=null;
         }else if(slow==fast){
             
            slow=head;
        while(slow.next!=fast.next){
            slow=slow.next;
            fast=fast.next;
           }
         fast.next=null;     
      } 
    }
--------------------------------------------------------------------------------------------------------
5. Middle element of Linked list
                        public int mid() {
		Node slow = head;
		Node fast = head;

		while (fast.next != null && (fast.next).next != null) { // in even case it gives 1st mid
			// while(fast!=null&&fast.next!=null) { // in even case it gives 2nd mid
			slow = slow.next;
			fast = (fast.next).next;
		}
		return slow.data;
	}

--------------------------------------------------------------------------------------------------------
6.  Reverse Nodes in k-Group  O(N),S(1)->https://www.youtube.com/watch?v=Of0HPkk3JgI
  public ListNode reverseKGroup(ListNode head, int k) {
       if(head==null||k==1){
           return head;
       }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
       
        ListNode curr=dummy,pre=dummy,next=dummy;
        int count=0;
        while(curr.next!=null){
            count++;
            curr=curr.next;
        }  
To not reverse last nodes if rem node are less than k
-------------------------------->
        while(count>=k){
            curr=pre.next;
            next=curr.next;
            for(int i=1;i<=k-1;i++){ //as we want to change k-1 links
                curr.next=next.next;
                next.next=pre.next;
                pre.next=next;
                next=curr.next;               
            }
            pre=curr;
            count-=k;
                
        }
To Reverse the last nodes even if rem nodes are less than k
-------------------------------->
 while(count>=k){
            if(count>=0){  // change it to k to covert it for upper task
            curr=pre.next;
            next=curr.next;
            for(int i=1;i<=k-1 && curr.next!=null;i++){ //as we want to change k-1 links
                curr.next=next.next;
                next.next=pre.next;
                pre.next=next;
                next=curr.next;               
            }
            pre=curr;              
            count-=k; 
            continue;    
          }
            k = count;   
            curr=pre.next;
            next=curr.next;
            for(int i=1;i<=k-1 && curr.next!=null;i++){ //as we want to change k-1 links
                curr.next=next.next;
                next.next=pre.next;
                pre.next=next;
                next=curr.next;               
            }
            pre=curr; 
            break;                    
        }    
-------------------------------->
        return dummy.next;  
    }

### Reverse K alternate nodes
-> https://www.techiedelight.com/reverse-alternate-group-k-nodes-linked-list/

public static Node reverse(NodeWrapper curr, int k)
    {
        // maintain a `prev` pointer
        Node prev = null;
 
        // traverse the list and reverse first `k` nodes
        while (curr.node != null && k-- > 0)
        {
            // tricky: note the next node
            Node next = curr.node.next;
 
            // fix the `curr` node
            curr.node.next = prev;
 
            // advance the two pointers
            prev = curr.node;
            curr.node = next;
        }
 
        // return node at the front
        return prev;
    }
 
    // Function to skip `k` nodes in a given linked list. Note that the
    // linked list is passed by reference using `NodeWrapper` class.
    public static Node skipKNodes(NodeWrapper curr, int k)
    {
        Node prev = null;
 
        while (curr.node != null && k-- > 0)
        {
            prev = curr.node;
            curr.node = curr.node.next;
        }
 
        return prev;
    }
 
    // Recursive function to reverse every alternate group of `k` nodes
    // in a linked list
    public static Node reverseAlternatingKNodes(Node head, int k)
    {
        Node prev = null;
 
        // Wrap current node, so its reference can be changed inside the
        // `reverse()` and `skipKNodes()` method
        NodeWrapper curr = new NodeWrapper(head);
 
        // traverse the whole list
        while (curr.node != null)
        {
            // curr would be the last node in the reversed sublist
            Node lastNode = curr.node;
 
            // reverse next `k` nodes and get their head
            Node frontNode = reverse(curr, k);
 
            // update head pointer after first `reverse()` call
            if (prev == null) {
                head = frontNode;
            }
            // for subsequent calls to `reverse()`, link the reversed sublist
            // with the rest of the list
            else {
                prev.next = frontNode;
            }
 
            // link the last node with the current node
            lastNode.next = curr.node;
 
            // skip next `k` nodes
            prev = skipKNodes(curr, k);
        }
 
        // return head node
        return head;
    }
--------------------------------------------------------------------------------------------------------
7. Delete nodes having greater value on right
Node DeleteNodeRightLarger(Node head){
        //Reverse the linkedlist for easy intuition
        head=reverseLL(head);
    
        Node curr=head.next;
        Node max=head;
        while(curr!=null){
            if(max.data<=curr.data){
                max=curr;
                curr=curr.next;
            }else{
                curr=curr.next;
                max.next=curr;
            }
        }
        max.next=null;
        head=reverseLL(head);
        return head;
    }

--------------------------------------------------------------------------------------------------------
8. Add two linked list in S(1)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
         ListNode head=l1;  //we will store the ans in l1
         ListNode prev=null; //this will help to join the link if l1 is smaller than l2
        
        int carry=0;
        while(l1!=null && l2!=null){
            int sum=l1.val+l2.val+carry;
            carry=sum/10;
            l1.val=sum%10;
            prev=l1;  //acts like a pointer
            
            l1=l1.next;
            l2=l2.next;
        }
        
        if(l2!=null){
            prev.next=l2;  //linking as l2 is bigger than l1
            l1=l2; //now assigning l1 as l2 because we don't want to make a new node-(using space)
        }
        
        while(l1!=null){
        int sum=l1.val+carry;
        carry=sum/10;
        l1.val=sum%10;
        prev=l1;
        l1=l1.next;            
        }
        
        if(carry!=0){
            prev.next=new ListNode(carry);
        }
       return head;
    }
# Add one to linked list
-> firstly reverse the linked list
->add 1 using the same method as above
-> Again reverse the linked list
--------------------------------------------------------------------------------------------------------
9. Remove duplicates from sorted List O(N) S(1)
  public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode prev=head;
        ListNode curr=prev.next;
        
        while(curr!=null){
            if(prev.val==curr.val){
                curr=curr.next;
                prev.next=curr;
            }else{
                prev=curr;
                curr=curr.next;
            }
        }
        return head;
    }
 #) Delete all occurences of duplicates  (LC-82)

  public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null)return head;
        
    ListNode dummy = new ListNode(0), curr = head, prev = dummy;
        prev.next = curr;
        while(curr != null) {
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;    //while loop to find the last node of the dups.
            }
            if (prev.next != curr) { //duplicates detected.
                prev.next = curr.next; //remove the dups.
                curr = curr.next;     //reposition the curr pointer.
            } else { //no dup, move down both pointer.
                prev = prev.next;
                curr = curr.next;
            }

        }
        return dummy.next;
    }    
--------------------------------------------------------------------------------------------------------
10. Remove duplicates from Unsorted List O(N) S(N)
//Don't use Hashmap it  will give TLE
 public Node removeDuplicates(Node head) 
    {
        Set<Integer>set=new HashSet<>();
        
        Node prev= null;
        Node curr= head;
        while(curr!=null){
            if(!set.contains(curr.data)){
                set.add(curr.data);
                prev=curr;
                curr=curr.next;
            }else{
                curr=curr.next;
                prev.next=curr;
            }
        }
        return head;
    }
--------------------------------------------------------------------------------------------------------
11. Intersection point in two linked list
Intuition-> 
      a-->   o-o-o-o-o
		              \
		               o-o-o
          	          /	      
      b-->       o-o-o	

->Suppose there are two sprinters 'b' started with startline whereas 'a' before startline(eg 2km behind the startline) now they start running and at some time refree see that this is unfair so he let 'b' first finish the race so when 'b' reaches end 'a' is exactly the diff(a-b) behind him. now refree let 'b' to cover the extra 2km distance by starting running from 'a's start point. in the mean time 'a' reaches to the end. at this position both start with exact same place. when we put 'a' at 'b's start point.
if (distA=distB) then 1 traversal.
if (distA!=distB) then 2 traversal.	

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       
        ListNode first=headA;
        ListNode second=headB;
        while(first!=second){
            first=(first==null)?headB:first.next;
            second=(second==null)?headA:second.next;
        }
        return first;
    }
--------------------------------------------------------------------------------------------------------
12. Intersection elements of 2 sorted linked list
 public static Node findIntersection(Node head1, Node head2)
    {
        Node dummy = new Node(0);
        Node head=dummy;
        
        while(head1!=null&&head2!=null){
            if(head1.data<head2.data){
                head1=head1.next;
            }else if(head1.data>head2.data){
                head2=head2.next;
            }else{
                dummy=addToLast(dummy,head1.data);
                head1=head1.next;
                head2=head2.next;
            }
        }
        head=head.next; //as first element is 0 in dummy;
        return head;
    }
    public static Node addToLast(Node head,int val){
     Node nn=new Node(val);
     head.next=nn;
     return nn;
    }

--------------------------------------------------------------------------------------------------------
13. MergeSort LinkedList O(nLogn) S(1)
public ListNode MergeSort(ListNode head){
        if(head==null||head.next==null){
            return head;    
        }
        
        ListNode mid=midNode(head);
        ListNode nhead=mid.next;
        mid.next=null;
        
        ListNode fh=MergeSort(head);
        ListNode sh=MergeSort(nhead);
    
        return MergeLL(fh,sh);
    }
    
    public ListNode midNode(ListNode head){
        ListNode fast= head;
        ListNode slow= head;
        
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        
        return slow;
    }
    //Merge Sort in constant Space complexity
    public ListNode MergeLL(ListNode l1,ListNode l2){
        ListNode dummy=new ListNode(0);
        ListNode prev=dummy;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                prev.next=l1;
                l1=l1.next;
            }else{
                prev.next=l2;
                l2=l2.next;
            }
            prev=prev.next;
        }
        
        prev.next=(l1!=null)?l1:l2;
        return dummy.next;
    }
--------------------------------------------------------------------------------------------------------
14. check for palindrome
 public boolean isPalindrome(ListNode head) {        
        if(head==null||head.next==null){
            return true;
        }
       ListNode slow=head;
       ListNode fast=head;
       while(fast.next!=null && fast.next.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }
       //reverse the right half
       slow.next=reverseLL(slow.next);
       
       slow=slow.next;
       
       ListNode dummy=head;
       
       while(slow!=null){
           if(dummy.val!=slow.val){
               return false;
           }
           slow=slow.next;
           dummy=dummy.next;
       }
       return true;
    } 
--------------------------------------------------------------------------------------------------------
15. Odd Even Linked List
 public ListNode oddEvenList(ListNode head) {
     ListNode odd=new ListNode(0);
     ListNode even=new ListNode(0);
     ListNode evenT=even;
     ListNode oddT=odd;
     ListNode curr=head; 
        
        int i=1;
        while(curr!=null){
            if(i%2==0){
                evenT.next=curr;
                evenT=evenT.next;
            }else{
                oddT.next=curr;
                oddT=oddT.next;
            }
            curr=curr.next;
            i++;
        }
                
        oddT.next=even.next;
        evenT.next=null;   
        
        return odd.next;           
    }
--------------------------------------------------------------------------------------------------------
15. Copy List With Random Pointer.
-> Firstly you should know about 
Deep copy-> suppose we have some data in google drive and we gave it to someone he downloaded it and then make changes in it, these changes will not reflect in others.(New address)
Shallow copy->suppose the person have given the link of google drive, now any of the two if make some changes then it would reflect in the original one.(Same address)
->In this Question we have to make a deep copy of the given linked list

Approach 1) O(N)-S(N)->https://www.youtube.com/watch?v=deaZgauZVco
  public Node copyRandomList(Node head) {
        HashMap<Node,Node>map=new HashMap<>();
        
        Node nHead=new Node(0);
        Node prev=nHead;
        
        Node curr=head;
        while(curr!=null){
            Node nn=new Node(curr.val);
            prev.next=nn;
            map.put(curr,nn);
            curr=curr.next;
            prev=prev.next;
        }

        nHead=nHead.next;
        Node c1=head;
        Node c2=nHead;
        while(c1!=null){
            c2.random=(c1.random!=null)?(map.get(c1.random)):null;
            c1=c1.next;
            c2=c2.next;
        }
        return nHead;        
    }

Approach 2) O(N)-S(1)->https://www.youtube.com/watch?v=VNf6VynfpdM
public Node copyRandomList(Node head) {
        Node itr=head;
        Node front=head;
      // First round: make copy of each node,
     // and link them together side-by-side in a single list.
    
        while(itr!=null){
          front =itr.next;
          Node nn=new Node(itr.val);
          itr.next=nn;
          nn.next=front;
          itr=front;         
        }
        
        // Second round: assign random pointers for the copy nodes.
        itr=head;
        while(itr!=null){
            if(itr.random!=null){
                itr.next.random=itr.random.next;
            }
            itr=itr.next.next;
        }
        
        // Third round: restore the original list, and extract the copy list.
        Node pseudoHead=new Node(0);
        itr=head;
        Node copy=pseudoHead;
        while(itr!=null){
           front=itr.next.next;
            
            //extract the copy
            copy.next=itr.next;
            copy=copy.next;
            
            //restore the original list
            itr.next=front;
            
            itr=front;
        }
        return pseudoHead.next;
    }

--------------------------------------------------------------------------------------------------------
16. Remove Nth Node from last
 public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next==null){
            return null;
        }
        
        ListNode fast=head;
    	for(int i=0;i<n;i++){
    	    fast=fast.next;
    	}
    	
    	ListNode dummy=new ListNode(0);
        ListNode prev=dummy;
        dummy.next=head;
        ListNode slow=head;
    	while(fast!=null){
            prev=slow;
    	    fast=fast.next;
    	    slow=slow.next;
    	}
        prev.next=slow.next;
    	return dummy.next;
    }

--------------------------------------------------------------------------------------------------------
17. Split list to parts
 public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[]result=new ListNode[k];
        
        if(root==null){
         return result;   
        }
        
        int length=0;
        ListNode temp=root;
        while(temp!=null){
            temp=temp.next;
            length++;
        }
        
        int eachlength=length/k;
        int extralength=length%k;
        
        int index=0;
        ListNode curr=root;
        while(curr!=null){
            ListNode head=curr;
            
            int diff=(extralength<=0)?0:1; //as we are using this extra length to divide it evenly
                                           //so we need to give each part only 1 extra length 
            for(int i=0;i<eachlength+diff-1;i++)
                curr=curr.next;
            
            ListNode xyz=curr.next;
            curr.next=null;
            curr=xyz;
            
            result[index++]=head;
            extralength--;
        }
        return result;   
    }
--------------------------------------------------------------------------------------------------------
18. Flattening a Linked List
->intuition=>we simply flatten the last two using mergeLL function and the resultant would be flatten with current second last. and so on
 Node flatten(Node root)
    {
	    if(root==null||root.next==null){
	        return root;
	    }
	    
	    root.next=flatten(root.next);
	                   //second last , last  and so on     
	    root= mergeLL(root,root.next);
	    return root;
    }
    
    Node mergeLL(Node a,Node b){
        
        Node temp=new Node(0);
        Node res=temp;
        
        while(a!=null && b!=null){
            if(a.data<b.data){
                temp.bottom=a;
                temp=temp.bottom;
                a=a.bottom;
            }else{
                temp.bottom=b;
                temp=temp.bottom;
                b=b.bottom;
            }
        }
        if(a!=null)temp.bottom=a;
        else temp.bottom=b;
        
        return res.bottom;
    }
--------------------------------------------------------------------------------------------------------
19. First Non-repeating character in a stream.
 public String FirstNonRepeating(String A)
    {
	    StringBuilder str=new StringBuilder();
		Queue<Character> q = new LinkedList<>();
		int[] arr = new int[26];
		for (int i = 0; i < A.length(); i++) {
			char ch = A.charAt(i);
			q.add(ch);
			arr[ch - 'a']++;
			while (!q.isEmpty()) {
				if (arr[q.peek() - 'a'] > 1)
					q.remove();
				else
					break;
			}
			if (q.isEmpty()) {
				str.append("#");
			} else {
				str.append(q.peek());
			}
		}
		return str.toString();
    }
--------------------------------------------------------------------------------------------------------
20. Reorder List (Fold List) in constant space
 Node reorderlist(Node head) {
       
        if(head==null||head.next==null){
            return head;
        }
       Node slow=head;
       Node fast=head;
       while(fast.next!=null && fast.next.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }
       //reverse the right half
       Node head2=reverseLL(slow.next);
       slow.next=null;
       
       Node head1=head;
       
       Node dummy=new Node(0);
       Node prev=dummy;
        int i=0;
        while(head1!=null || head2!=null){
            if(i%2==0){
                if(head1!=null){
                    prev.next=head1;
                    head1=head1.next;
                    prev=prev.next;
                }
            }else{
                if(head2!=null){
                    prev.next=head2;
                    head2=head2.next;
                    prev=prev.next;
                }
            }
            i++;
          
        }
       return dummy.next;
    }
--------------------------------------------------------------------------------------------------------
21. Merge K sorted Lists
Approach 1)Divide & Conquer -O(nkLogk)
public ListNode mergeKSortedLists(ListNode[]list,int si,int ei){
        if(si>ei){
            return null;
        }
        if(si==ei){
            return list[si];
        }
        int mid=(si+ei)/2;
        
        ListNode fh=mergeKSortedLists(list,si,mid);
        ListNode sh=mergeKSortedLists(list,mid+1,ei);
        
        return merge2lists(fh,sh); 
    }

Approach 2) Priority Queue - O(nkLogk),S(K)
  public ListNode mergeKLists(ListNode[] lists) {
    
        PriorityQueue<ListNode>pq=new PriorityQueue<>((a,b)->(a.val-b.val));
        
       for(ListNode l:lists){
           if(l!=null)
           pq.add(l);
       }
        
        ListNode dummy=new ListNode(0);
        ListNode prev=dummy;
        while(!pq.isEmpty()){
            ListNode rn=pq.remove();
            prev.next=rn;
             prev=prev.next;
            rn=rn.next;
            if(rn!=null){
                pq.add(rn);
            }
           
        }
        prev.next=null;
        return dummy.next;
    }
--------------------------------------------------------------------------------------------------------
22. Multiply 2 LinkedLists
//Just Dry run normal Mulitplication for better understanding
public static ListNode multiplyTwoLL(ListNode l1, ListNode l2) {
       l1=reverseLL(l1);
       l2=reverseLL(l2);
       
       ListNode dummy=new ListNode(-1);
       ListNode ans_itr=dummy;
       ListNode l2_itr=l2;
       
       while(l2_itr!=null){
           ListNode pro=multiplyLLwithDigit(l1,l2_itr.val);
           l2_itr=l2_itr.next;
           
           addTwoLL(pro,ans_itr);   
           ans_itr=ans_itr.next;
       }
       
       return reverseLL(dummy.next);
    }
    
    public static ListNode multiplyLLwithDigit(ListNode l1,int dig){
        ListNode dummy=new ListNode(-1);
        ListNode ac=dummy;
        ListNode curr=l1;
        
        int carry=0;
        while(curr!=null||carry!=0){
            int sum=carry+((curr!=null)?curr.val*dig:0);
            int rem=sum%10;
            carry=sum/10;
            
            ac.next=new ListNode(rem);
            if(curr!=null)
              curr=curr.next;
            ac=ac.next;
        }
        return dummy.next;
    }
    public static void addTwoLL(ListNode head,ListNode ansItr){
        ListNode c1=head; //the list to be added with
        ListNode c2=ansItr; //the resultant list of the previous mulitplication
        
        //since c1 can be greater than or equal to c2(ansItr) so just checking for c1 condition only
        int carry=0;
        while(c1!=null||carry!=0){
           int sum=carry+(c1!=null?c1.val:0) + (c2.next!=null?c2.next.val:0);
           int rem=sum%10;
           carry=sum/10;
           
           if(c2.next!=null)c2.next.val=rem;
           else c2.next=new ListNode(rem);
           
           if(c1!=null)c1=c1.next;
           c2=c2.next;
        }
    }
    
     public static ListNode reverseLL(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        
    ListNode curr=head.next;
    ListNode prev=head;
    ListNode ahead;
    while(curr!=null){
        ahead=curr.next;
        curr.next=prev;
        prev=curr;
        curr=ahead;
    }
    
    ListNode temp=head;
    head=prev;
    temp.next=null;
        return head;
    }
--------------------------------------------------------------------------------------------------------
23. Reverse a Doubly Linked List
Logic-> just reverse the linked list using next pointers.
and then take it as head and reverse again using prev pointers
--------------------------------------------------------------------------------------------------------
24. Find pairs with a given sum in a DLL 
	static void pairSum(Node head, int x) {
		Node first = head;
		Node second = head;
		while (second.next != null)
			second = second.next;

		// To track if we find a pair or not
		boolean found = false;

		while (first != second && second.next != first) {
			if ((first.data + second.data) == x) {
				found = true;
				System.out.println("(" + first.data + ", " + second.data + ")");
				first = first.next;
				second = second.prev;
			} else {
				if ((first.data + second.data) < x)
					first = first.next;
				else
					second = second.prev;
			}
		}
		if (found == false)
			System.out.println("No pair found");
	}
--------------------------------------------------------------------------------------------------------
25. Count triplets in a sorted doubly linked list whose sum is equal to to a given value x.
static int countTriplets(Node head, int x) {
		if (head == null)
			return 0;

		Node current, first, last;
		int count = 0;

		last = head;
		while (last.next != null)
			last = last.next;

		for (current = head; current != null; current = current.next) {
			first = current.next;
			count += countPairs(first, last, x - current.data);
		}
		return count;
	}
--------------------------------------------------------------------------------------------------------
26. Rotate List By k places
  public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null||k==0){
            return head;
        }
        
        int len=1;
        ListNode curr=head;
        while(curr.next!=null){
            curr=curr.next;
            len++;
        }
        
        //make it circular
        curr.next=head;
        
        k=len-k%len;
        while(k-->0)curr=curr.next;
        
        head=curr.next;
        curr.next=null;
            
        return head;        
    }
--------------------------------------------------------------------------------------------------------
27. Rotate Doubly linked list by k places
	static void rotate(int N) {
		if (N == 0)
			return;

		Node current = head;

		int count = 1;
		while (count < N && current != null) {
			current = current.next;
			count++;
		}
		if (current == null) // means n is greater than or equal to length of list
			return;

		Node NthNode = current; // it(nth) can maximum be tail

		while (current.next != null)
			current = current.next;

		current.next = head; // making list circular

		(head).prev = current;
		head = NthNode.next;
		(head).prev = null;
		NthNode.next = null;
	}
--------------------------------------------------------------------------------------------------------
28. Swap Nodes in pairs (LC-24)

M1) Separate even list and odd list and join them alternatively <- 2 traversals

M2) One Traversals using 3 pointers

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode point = dummy;
    while (point.next != null && point.next.next != null) { 
        ListNode swap1 = point.next;
        ListNode swap2 = point.next.next;
        point.next = swap2;
        swap1.next = swap2.next;
        swap2.next = swap1;
        point = swap1;
    }
    return dummy.next;
}

M3) Using Recursion
 public ListNode swapPairs(ListNode head) {
        if ((head == null)||(head.next == null))
            return head;
        ListNode n = head.next;
        head.next = swapPairs(head.next.next);
        n.next = head;
        return n;
    } 
-----------------------------------------------------------------------------------------------------
29. Swapping Nodes in a Linked List (LC-1721)

-> Just find out the (prev-curr-next) of first-k and last-k node.
-> There will be 3 cases of swapping 
a) General case both are far away from each other.
b) first and second crossed each other.
c) Both are adjacent nodes.

 public ListNode swapNodes(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode firstPrev = dummy;
        for (int i = 0; i < k - 1; i++) {
            firstPrev = firstPrev.next;
        }

        ListNode secondPrev = dummy;
        ListNode advanced = firstPrev.next.next;
        while (advanced != null) {
            secondPrev = secondPrev.next;
            advanced = advanced.next;
        }

        ListNode first = firstPrev.next;
        ListNode second = secondPrev.next;
        ListNode firstNodeAfter = first.next;
        ListNode secondNodeAfter = second.next;
        
        if (second.next == first) {  //case when second node crossed first like eg: [5,2] and k = 2;
            secondPrev.next = first;
            first.next = second;
            second.next = firstNodeAfter;
        } else if (secondPrev == first) {  //in case of adjacent nodes.
            firstPrev.next = second;
            second.next = first;
            first.next = secondNodeAfter;
        } else {            // general case
            firstPrev.next = second;
            second.next = firstNodeAfter;
            secondPrev.next = first;
            first.next = secondNodeAfter;
        }

        return dummy.next;
    }
--------------------------------------------------------------------------------------------------------
30. Subtraction in LinkedList
->

class Solution {
    Node subLinkedList(Node l1, Node l2) {

        l1 = skipLeadingZero(l1);
        l2 = skipLeadingZero(l2);

        int s1 = size(l1);
        int s2 = size(l2);

        if (s1 < s2) return subLinkedList(l2, l1);
        else if (s1 == s2) {
            if (sumDigit(l1) < sumDigit(l2))
                return subLinkedList(l2, l1);
        }

        l1 = reverse(l1);
        l2 = reverse(l2);

        Node ansHead, ansTail;
        ansHead = ansTail = new Node(-1);

        while (l2 != null && l1 != null) {
            if (l1.data < l2.data) {
                l1.data += 10;
                adjustBorrow(l1.next);
            }

            ansTail.next = new Node(l1.data - l2.data);
            ansTail = ansTail.next;

            l1 = l1.next;
            l2 = l2.next;
        }

        ansTail.next = l1;

        ansHead = reverse(ansHead.next);
        ansHead = skipLeadingZero(ansHead);

        return (ansHead == null) ? new Node(0) : ansHead;
    }

    static long sumDigit(Node head) {
        long s = 0;
        while (head != null) {
            s = s + head.data;
            head = head.next;
        }
        return s;
    }

    static int size(Node head) {
        int s = 0;
        while (head != null) {
            s++;
            head = head.next;
        }
        return s;
    }

    static Node reverse(Node head) {
        if (head == null || head.next == null) return head;

        Node tail = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }

    void adjustBorrow(Node node) {
        while (node != null && node.data == 0) {
            node.data = 9;
            node = node.next;
        }
        if (node != null)
            node.data--;
    }

    Node skipLeadingZero(Node head) {
        while (head != null && head.data == 0) {
            head = head.next;
        }
        return head;
    }
}

----------
# Can we reverse a linked list in less than O(n)?
->https://www.geeksforgeeks.org/can-we-reverse-a-linked-list-in-less-than-on/

--------------------------------------------------------------------------------------------------------
#Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
->https://www.geeksforgeeks.org/why-quick-sort-preferred-for-arrays-and-merge-sort-for-linked-lists/
=> MergeSort for linked list can be done in constant space, and For Arrays QuickSort is Best as it is an inplace sorting algorithm so doesn't require extra space which kind of reduces the complexity also.