merged linked list in C

This question was asked to me in an interview: There are two header of two linked lists. There is a merged linked list in c where in the second linked list is merged into the first one at some point. How could we identify the merging point and what is the complexity of 开发者_运维百科finding that point ?

Could anybody please help?

---

O(n)

search = list1->header;
if (mixed->header == list1->header) search = list2->header;

while (mixed->next != search) mixed = mixed->next;

---

Edit: new name for variables and a few comments

/* search is what we want to find. Here it's the head of `list2` */
search = list2->header;
/* unless the merging put `list2` first; then we want to search for `list1` */
if (mixed->header == list2->header) search = list1->header;

/* assume (wrongly) that the header for the mixed list is the merge point */
mergepoint = mixed->head;

/* traverse the mixed list until we find the pointer we're searching */
while (mergepoint->next != search) mergepoint = mergepoint->next;
/* mergepoint now points to the merge point */

---

Update: This assumes the Y-shaped joining of two linked lists as described better in Steve Jessop's post. But I think the description of the problem is sufficiently ambiguous that various interpretations are possible, of which this is only one.

---

This can be done with a single pass through one list plus a partial pass through the other. In other words, it's O(n).

Here's my proposed algorithm:

Create a hashmap. (Yes, this is busywork in C if you don't have a library handy for it). The keys will be pointers to the items in List1 (i.e. the head pointer and each link). The values will be integers denoting the position, i.e. distance from the head of List1.

Run through List1, keeping track of the position, and hash all your pointers and positions.

Run through List2, keeping track of the position, and find the first pointer that occurs in the hashmap.

At this point, you'll know the position in List2 of the first node common to both lists. The hashmap entry will also contain the position in List1 of that same node. That will nicely identify your merge point.

---

Do you mean you have a Y-shape, like this:

list1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

Where A .. Z are singly-linked list nodes. We want to find the "merge point" E, which is defined to be the first node appearing in both lists. Is that correct?

If so, then I would attach the last node of list2 (F) to the first node of list2 (X). This turns list2 into a loop:

list2 : X -> Y -> Z -> E -> F -> X -> ...

But more importantly:

list1 : A -> B -> C -> D -> E -> F -> X -> Y -> Z -> E -> ...

This reduces the question to a previously-solved problem, which can be solved in O(n) time and O(1) additional storage.

But reading your question, another possibility is that by "merge" you mean "insert". So you have two lists like this:

list1: A -> B -> C

list2: D -> E -> F

and then another completely separate list:

list3: A -> B -> D -> E -> F -> C

where this time, A .. F are the values contained in the list, not the nodes themselves.

If the values are all different, you just need to search list3 for D (or for the later of D and A, if you don't know which list it was that was copied into the other). Which seems like a pointless question. If values can be repeated, then you have to check for the full sequence of list2 inside list3. But just because you find "DEF" doesn't mean that's where list2 was inserted - maybe "DEF" already occurred several times in list1 beforehand, and you've just found the first of those. For instance if I insert "DEF" into "ABCDEF", and the result is "ABCDEFDEF", then did I insert at index 3 or at index 6? There's no way to tell, so the question can't be answered.

So, in conclusion, I don't understand the question. But I might have answered it anyway.

---

If the question means list2 contained in list1 (that is list2 points somewhere in the middle of list1), then it is easy - just walk list1 and compare pointers until you reach list2.

However such interpretation does not make much sense, because by inserting list2 into the list1 (like 1 1 2 2 1), you would also modify list2 - the last 1 becomes part of list2.

So I will assume the question is about the Y shape:

list1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

This can be solved using hashtable as Carl suggested.

Solution without a hashtable would be this:

1. Walk list1 and disconnect all its pointers as you go
2. Walk list2. When it ends, you've reached the junction point
3. Repair the pointers in list1

Disconnecting and repairing pointers in list1 can be done easily using recursion:

Diconnect(node)
{
    if (node->next == NULL)
      walk list2 to its end, that is the solution, remember it
    else
    {
       tmp = node->next;
       node->next = NULL;
       Disconnect(tmp);
       node->next = tmp;  // repair
    }
}

Now call Disconnect(list1).

That is recurse down list1 and disconnect pointers. When you reach end, execute step 2 (walk list2 to find junction), repair pointers when returning back from recursion.

This solution modifies list1 temporarily, so it is not thread safe and you should use a lock around the Disconnect(list1) call.

---

//try this code for merge

   void mergeNode(){  
          node *copy,*current,*current1;

          free(copy);
      merge=NULL;
     current=head;
   current1=head1;
    while(current!=NULL){
    if(merge==NULL){
        node *tmp;
        tmp=(node*)malloc(sizeof(node));
        tmp->data=current->data;
        tmp->link=NULL;
        merge=tmp;
    }
    else{
        copy=merge;
        while(copy->link!=NULL)
            copy=copy->link;
        node *tmp;
        tmp=(node*)malloc(sizeof(node));
        tmp->data=current->data;
        tmp->link=copy->link;
        copy->link=tmp;
    }
    current=current->link;
}
while(current1!=NULL){
    copy=merge;
    while(copy->link!=NULL)
        copy=copy->link;
    node *tmp;
    tmp=(node*)malloc(sizeof(node));
    tmp->data=current1->data;
    tmp->link=copy->link;
    copy->link=tmp;
    current1=current1->link;
}
display(merge);

}

---

Sorry if my answer seems too simple, but if you have two linked list which are identified by a header and you join them, so that

A -> B -> C -> D is the first list, and

1 -> 2 -> 3 -> 4 is the second, then suppose

A -> B -> C -> 1 -> 2 -> 3 -> 4 -> D is the result

then to find the merging point you need to go through the final list until you find the second header (the 1). Which goes in O(n1) worst case, where n1 is the number of elements of the first list (this happens if the second list is merged at the end).

That's how I would intend the question. The reference to the C language would probably mean that you have no 'object' or pre-packaged data structure, unless specified.

[update] as suggested by Sebastian, if the two list above have the same elements my solution won't work. I suspect that this is where the C language comes into action: you can search for the address of the first element of the second list (the head). Thus the duplicates objection won't hold.

---

Well, there are several approaches to solve this problem.

Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list

Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.

while(head1)
{
cur2=head2;
while(cur2)
{
    if(cur2==head1)
        return cur2;
    cur2=cur2->next;
}
head1=head1->next;
}

Time Complexity: O(N*M)
Space Complexity: O(1)

Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].

Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.

Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 6: [A better approach]
1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)

Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)

---

Trivial solution is obviously O(N+M). Hm.. What could be better. You can go from start to end of the list or vice versa. When you have a threads, you can go these directions at the some time, so should be a litter bit quicker.