Find merge point of two linkedlists - solution 1, Java

Find merge point of two linkedlists - solution 1

/*
    Find merge point of two linkedlists
    Using Set, Overall time complexity: O(N log N + M log N)
    
    Author: Jayesh Chandrapal
*/

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        // Create two merge linked lists
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
        Node node5 = new Node(50);
        Node node6 = new Node(60);
        
        Node list1 = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node5;
        node5.next = node6;
        
        Node list2 = node4;
        node4.next = node3;
        
        /*
            10 -> 20
            
                     -> 30 -> 50 -> 60
            
                  40
                  
            Merge point : 30
        */
        
        // Find and display merge node
        System.out.println("Merge node: " + findMergePoint(list1, list2));
        
    }
    
    /*
        Returns merge node for given two linked lists.
        Overall time complexity: O(N log N + M log N)
        where N = list1 size, M = list2 size.
        
        @param: list1 first linked list head node
        @param: list2 second linked list head node
        
        @return Node merge node where two given linked lists merge.
                Return null if linked lists do not merge.
    */
    public static Node findMergePoint(Node list1, Node list2) {
        Set<Node> visited = new HashSet<Node>();
        Node mergeNode = null;
        
        Node current = list1;
        while(current != null) {     // O(N * log N)
            visited.add(current);
            current = current.next;
        }
        
        current = list2;
        while(current != null) {    // O(M * log N)
            if(visited.contains(current)) {
                mergeNode = current;
                break;
            }
            current = current.next;
        }
        
        return mergeNode;
    }
}

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this(data, null);
    }
    
    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    
    @Override
    public String toString() {
        return String.valueOf(data);
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development