Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.6 kB
2
Indexable
Never
class Solution
{
    public static Node trimFirstZeros(Node head){
        Node temp = head;
        while(temp != null && temp.data == 0){
            temp = temp.next;
        }
        return temp;
    }
    public static int length(Node head){
        Node temp = head;
        int count = 0;
        while(temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
    public static Node reverse(Node head){
        if(head == null || head.next == null){
            return head;
        }
        
        Node current = head;
        Node prev = null;
        while(current != null){
            Node nxt = current.next;
            current.next = prev;
            prev = current;
            current = nxt;
        }
        return prev;
    }
    public static Node subtractTwoLinkedList(Node l1, Node l2){
        Node dummy = new Node(-1);
        Node temp = dummy;
        
        Node i = l1;
        Node j = l2;
        int borrow = 0;
        
        while(i != null){
            int diff = borrow + i.data - (j != null ? j.data : 0);
            if(diff < 0){
                diff = diff + 10;
                borrow = -1;
            }
            else{
                borrow = 0;
            }
            
            i.data = diff;
            
            i = i.next;
            if(j != null) j = j.next;
        }
        
        Node ans = dummy.next;
        return l1;
    }
    public static Node subLinkedList(Node l1, Node l2)
    {
        // code here
        if(l1 == null && l2 == null) return null;
        if(l1 != null && l2 == null) return l1;
        
        l1 = trimFirstZeros(l1);
        l2 = trimFirstZeros(l2);
        
        int length1 = length(l1);
        int length2 = length(l2);
        
        if(length1 < length2){
            Node temp = l1;
            l1 = l2;
            l2 = temp;
        }
        if(length1 == length2){
            Node temp1 = l1;
            Node temp2 = l2;
            
            while(temp1.data == temp2.data){
                temp1 = temp1.next;
                temp2 = temp2.next;
                
                if(temp1 == null){
                    return new Node(0);
                }
            }
            if(temp2.data > temp1.data){
                Node temp = l1;
                l1 = l2;
                l2 = temp;
            }
        }
        
        l1 = reverse(l1);
        l2 = reverse(l2);
        
        Node ans = subtractTwoLinkedList(l1, l2);
        ans = reverse(ans);
        ans = trimFirstZeros(ans);
        return ans;
    }
}