We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Linked Lists
  4. Find Merge Point of Two Lists
  5. Discussions

Find Merge Point of Two Lists

Sort by

recency

|

1223 Discussions

|

  • himanshuramoliya
     + 0 comments

    constrain should mention that data would be positive only, or did I just find a bug :P

    int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode *ptr = head1;
    while (ptr) {
        ptr -> data = -1*(ptr->data);
        ptr = ptr -> next;
    }   
    ptr = head2;
    while (ptr) {
        if(ptr->data<0) return -1*(ptr->data);
        ptr = ptr->next;
    }
    return -1;
}

  • muhammadnabilas2
     + 1 comment

    The Constraint LIES:

    head1 != head2

    that is a lie. i fixed my code by allowing search for head it answered correctly.

    c++ solution:

    int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    auto first = head1;
    auto second = head2;
    while (first != second) {
        first = (first->next) ? first->next : head2;
        second = (second->next) ? second->next : head1;
    }
    // no merge, should never happend
    if (first == nullptr)
        throw -1;
    return first->data;
}

  • yaya00k8
     + 0 comments

    Simple Python code:

    def findMergeNode(head1, head2):
    A,B = head1, head2
    seen=[]

    while A:
            seen.append(A)
            A=A.next
    while B:
            if B in seen:
                return B.data
            else:
                B=B.next

    return None

  • mdsanz
     + 0 comments

    My Java 8 Solution

    static int getLength(SinglyLinkedListNode node) {
        int length = 0;
        
        while (node != null) {
            node = node.next;
            length++;
        }
        
        return length;
    } 
     
    static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        int length1 = getLength(head1);
        int length2 = getLength(head2);
        
        while (length1 > length2) {
            head1 = head1.next;
            length1--;
        }
        
        while (length2 > length1) {
            head2 = head2.next;
            length2--;
        }
        
        while (head1 != head2) {
            head1 = head1.next;
            head2 = head2.next;
        }
        
        return head1.data;
    }

  • emhhacker
     + 0 comments

    My Java solution with o(n) time and o(1) space:

    static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        //use two ptrs to track head1 and head2
        SinglyLinkedListNode first = head1;
        SinglyLinkedListNode second = head2;
        
        while(first != second){
            first = (first.next != null) ? first.next : head2;
            second = (second.next != null) ? second.next : head1;
        }
        
        return first != null ? first.data : -1; //no merge node found
    }