Need help on pseudocode/algorithm - linked list merge

Question

I saw below code as answer for merging two sorted lists in C , in one of the post.

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Can anyone please explain this to me as a pseudocode text? Not able to comment under same answer hence posting as new question.

Why bother with code as obtuse as this? There are plenty of implementations out there (including on Stack Overflow) that clearly express what's going on. — NPE, Aug 15 '13 at 05:48
I have been clear with other implementations and I wrote one of mine as well. But this one caught my eyes using pointer to pointer, so I want to understand. — Diwakar Sharma, Aug 15 '13 at 05:55
also http://stackoverflow.com/questions/5375688/how-does-pointer-dereferencing-work — NPE, Aug 15 '13 at 05:58
@DiwakarSharma... You are trying to swap pointers? Use `^` this... — someone, Aug 15 '13 at 06:20

score 0 · Accepted Answer · answered Aug 15 '13 at 07:45

First there's a preprocessor directive:

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

This means that as the preprocessor is preparing the translation unit for compilation, whenever it comes across SWAP_PTRS(a, b) it will replace it with

do { void *t = (a); (a) = (b); (b) = t; } while (0)

Let's unpack that. It's simply a function to swap a single pair of pointers a and b.

Since the loop is a do ... while loop it will execute before testing the loop condition. Inside the loop, a new void pointer t is declared. This is compatible with any type of pointer, so no matter what type of pointer a and b are, they are compatible with t.

Then it's a standard swap:

Assign a to t
Assign b to a
Assign t to b

After the swap, the loop condition is checked. Since it's 0, the condition evaluates to false and the do ... while loop ends. In other words, it will have been executed once and once only, which is what is needed, as the goal is just to swap one pair of pointers.

Here is the pseudocode for the actual MergeLists function.

Algorithm MergeLists
Receives: pointer to head node of linked list list1
    pointer to head node of linked list list2
Returns: pointer to head node of merged list

1. Declare pointer list for merged list and initialize to NULL
2. Declare pointer to pointer pNext and initialize it to the address of the merged list
3. if (list2 is NULL)  // empty list
    3.1 return list1   // nothing to merge
4. loop while list1 is not NULL
    4.1 if (data in list1 is greater than data in list2)
        4.1.1 swap list1 and list2
    4.2 set dereferenced value of pNext to list1
    4.3 set pNext to the address of the next node in list1
    4.4 set list1 to the dereferenced value of pNext // same as list1 = list1->next
5. end loop for list1
6. set the dereferenced value of pNext to list2
7. return list

This is rather difficult logic to follow. The heavy lifting is all in the while loop. Here's a breakdown:

There are two pointers to linked list nodes, list1 and list2. The first step in the while loop set the node that has the smaller data value as list1 and the other as list2. If needed, this is set using the SWAP_PTRS macro.

At the beginning, *pNext points to this list1 that has the smaller data value. The very first time through the loop, since *pNext is also list (the merged list), list will now point to the same place as well.

The next step resets pNext to the address of the next node in list1. This won't, however, change where list is pointing (pNext is a two-level pointer, and in this step we are changing where pNext is pointing, i.e., not where *pNext is pointing).

Then list1 is set to *pNext, i.e. to list1->next.

Then the loop goes into its next iteration with this new list1.

So basically it just keeps checking the data values of the nodes at the head of the lists, and adds the node with the smaller data value to the end of the merged list. When it reaches the end of either list, the loop will terminate and the rest of the nodes in the other list are appended to the end of the merged list.

Hope this makes sense! It is quite a nifty solution and would honestly be a lot easier to draw than it is to explain in words.

Yeah, I hope to see diagram for this badly :) Anyways your efforts have pushed some more clarity into my head — Diwakar Sharma, Aug 15 '13 at 19:31
I think the really difficult part to understand and explain is this: if `pNext` is a pointer to a pointer to a list node, then `*pNext`, i.e., the dereferenced value, is a pointer to a list node. — verbose, Aug 15 '13 at 19:33

Need help on pseudocode/algorithm - linked list merge

1 Answers1