Merge two sorted Linked List

general
1

I had a doubt in this problem: link
I am following this solution:

if((headA==NULL)&&(headB==NULL)
    return NULL;
if((headA!=NULL)&&(headB==NULL))
    return headA;
if((headA == NULL)&&(headB!=NULL))
    return headB;
if(headA->data < headB->data)
    headA->next = MergeLists(headA->next, headB);
else if(headA->data > headB->data)
{
    Node* temp = headB;
    headB = headB->next;
    temp->next = headA;
    headA = temp;
    headA->next = MergeLists(headA->next, headB);
}
return headA;

I get that when headA->data < headB->data then we simply move the headA pointer to the next node. But when headA->data > headB->data, then we create a temp pointer, point it where headA is pointing and move headB to next node.
What I don’t get is:

  1. How are the previous nodes of headA that were already sorted are linked to this newly created node temp(now headA) as there is no link mentioned in this code.

  2. Also, where is the headA pointing next? Is it at the current new temp node?

2

What you are doing here is that you are merging both the given sorted linked lists into List A.

Firstly

How are the previous nodes of headA that were already sorted are linked to this newly created node temp(now headA) as there is no link mentioned in this code.

Since the head of both the lists A and B is given, so the element of both the lists can be put into temp variable. We can traverse through the list using next pointer like ptra = ptra->next

Secondly,

If currently we are at the i-th element in the list A and j-th element in list B then:-

  1. if A[i] < B[j] then we need not do anything

  2. if A[i] > B[j] then we need to insert B[j] before A[i], that is why we are using temp variable there

There can be more cases but I just explained you the cases which you asked.

1 Like
3

Thanks for answering. But in the second condition as you said we insert the B[j] right before A[i], but there should be link from A[i-1] to B[j]. Can you please show that code where it links the previous node to the new node?

4

Simplest way would be to take two pointers for each list.

One pointer would be for current node and the other would be for previous node.

When current would be at A[i] then previous should be at A[i-1]. In this way you can do it.

1 Like
5

I really apreciate that you are replying to my silly questions. But can you point out in my code where the the previous node gets linked because I still can’t visualize it :frowning: