Q17 Subtraction in Linked List | Practice | GeeksforGeeks

//{ Driver Code Starts
// driver

import java.util.*;

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class GfG{
    
    static void printList(Node n){
        while(n!=null){
            System.out.print(n.data+" ");
            n = n.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            
            int n = sc.nextInt();
            int val = sc.nextInt();
            
            Node first = new Node(val);
            Node tail = first;
            for(int i=0; i<n-1; i++)
            {
                val = sc.nextInt();
                tail.next = new Node(val);
                tail = tail.next;
            }
            
            int m = sc.nextInt();
            val = sc.nextInt();
            
            Node second = new Node(val);
            tail = second;
            for(int i=0; i<m-1; i++)
            {
                val = sc.nextInt();
                tail.next = new Node(val);
                tail = tail.next;
            }
            
            Solution g = new Solution();
            Node res = g.subLinkedList(first, second);
            printList(res);
        }
    }
}

// } Driver Code Ends



/* Structure of Linked list node

class Node
{
	int data;
	Node next;
	Node(int d)
	{
		data = d;
		next = null;
	}
}

*/

class Solution
{
    
      static Node reverse(Node head)
    {
        Node prev = null;
        Node next = null;
        Node current = head;
        
        
        while(current != null){
            next = current.next;
            current.next = prev ;
            
            prev = current;
            current = next;
        }
        return prev;
    }
    
    static int length (Node head){
        int count = 0 ;
        Node curr = head;
        
        while(curr!=null){
            count++;
            curr=curr.next;
        }
        return count;
    }
    
//we have made function such that l1 is alway bigger than l2    
    static Node subtract(Node l1 , Node l2){

//reverse the LL's to perform substraction        
        Node curr1 = reverse(l1);
        Node curr2 = reverse(l2);

//make a dummy node and keep a borrow         
        int borrow = 0;
        Node dummyhead = new Node(-1);
        Node dummy = dummyhead;
        
        //l1 is bigger it will get to null later
        while(curr1 != null ){

        //find the difference            
            int sub = curr1.data - (curr2!= null ? curr2.data:0) -borrow;
        
//if diff >= 0 there will be no borrow            
            if(sub >= 0)
                borrow = 0;
            
            else{
                borrow =1;
                sub += 10;
            }  
            
            //adding to the dummy node
            Node temp = new Node(sub%10);
            dummy.next = temp;
            
            dummy = dummy.next;
            curr1 = curr1.next;
            
// LL2 is smaller it will get to null first so handled for that            
            if(curr2 != null) curr2 = curr2.next;
        }

//re-reversing the final answer         
        dummyhead = reverse(dummyhead.next);

//removing leading zeroes from the final answer         
        while(dummyhead!=null && dummyhead.data == 0)
        dummyhead = dummyhead.next;
        
        return dummyhead;
    }
    
    static Node subLinkedList(Node l1, Node l2)
    {   
//first remove the leading zeroes if any from both the LL     
        while(l1!=null && l1.data == 0)
        l1 = l1.next;
        
        while(l2!=null && l2.data == 0)
        l2 = l2.next;
        
//if any one is null return the second LL     
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        
//find lengths and whichever has greater length that will get subtracted from        
        int len1 = length(l1);
        int len2 = length(l2);
        

//write a subtract function and pass the greater,smaller LL in that order        
        if(len1 > len2)
        return subtract(l1,l2);
        
        else if( len2 > len1)
        return subtract(l2,l1);
        
//if lengths are same find the first greater number from left to right that will become the
// greater LL
        else{
            Node curr1 = l1;
            Node curr2 = l2;
            
            while(curr1!= null){
                
                if(curr1.data > curr2.data)
                return subtract(l1,l2);
                
                
                else if(curr2.data > curr1.data)
                return subtract(l2,l1);
                
                curr1 = curr1.next;
                curr2 = curr2.next;
            }
            
//if LL's are perfectly equal return 0 as node
            return new Node(0);
        }
    }
}