How does pointer dereferencing work?

#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;
}

This code is from here, the chosen answer of this question.

I cannot understand 3 lines here:

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

Can anyone kindly help me? Explain it for me?

Edited: Can I change these 2 lines:

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

to

 list = list-> next; 

---

From the start: You have two lists and a new list head which you will be returning. pnext points to that initially.

The code aims to do as few pointer reassignments as possible, so tries to keep the initial 'next' pointers of the input lists intact.

list1          pnext->list->Null
|
V
o->o->o...

list2
|
V
o->o->o...

Swap is there to ensure that the smaller element is the first of list1. What those lines does is:

Going step by step:

*pnext = list1;

Gets *pnext (which is list before the first iteration) to point to the node containing the smallest element:

list1
|
V
o->o->o...
^
|
list<-pnext

list2
|
V
o->o->o...

.

pnext = &list1->next;

Is the tricky part, as noted before & operator has low precedence. It's also hard to display graphically for it actually looks into part of a Node construct. Something like this though:

list1
|
V
o---->o->o...
^     ^
|     |
list  x<-pnext

list2
|
V
o->o->o...

where x is the next pointer of the o which list1 points to.

list1 = *pnext;

Advances the list1 head, as its first element is processed.

   list1<-pnext
   |
   V
o->o->o->...
^
|
list

list2
|
V
o->o->o->...

You have nothing to do with list from here on, for you want to return it as the head of the merged list.

The invariant there is pnext points to where the last processed element's next points to, which is where the smallest element from list1-2 should go. The interesting stuff happens with swaps, try to work out the exact proceedings yourself (hard to draw like this, and good exercise to understand what ** does). I might add it if I find a good way to draw it.

You cannot use list = list-> next; for it would do something like this:

   list1
   |
   V
o->o->o->...
   ^
   |
   list

list2
|
V
o->o->o->...

Which means you lose that lonely o (and everything else eventually as the loop progresses).

edit: The *pnext = list2; at the end does this:

Loop termination (state before the said statement):

         list1<-pnext
         |
         V
o->o->o->null
^
|
list

      o->o->o->...
      ^
      |
      list2

After the statement:

         list1
         |
         V              
o->o->o  Null
^     |
|     |
list  |
      V
      o->o->o->...
      ^
      |
      list2<-pnext

That statement appends the remaining list to the end of the list. Then Node* list is returned, pointing to the head of the merged list.

edit2:

And all the way, pnext would be better represented like this:

         list1
         |
         V              
o->o->o  Null
^     |
|     |<-pnext
list  |
      V
      o->o->o->...
      ^
      |
      list2

Which means it points to the next pointer of the last processed node.

---

pnext is a pointer to a pointer to a Node.

"*pnext" means you are working with the value pointed to by pnext. Thus:

*pnext = list1;

means that whatever pointer pnext was pointing to is now pointing to the same thing as list1.

---

The next line should be bracketed for clarity to this:

pnext = &(list1->next);

list1->next means you are accessing the next attribute of what list1 is pointing too, and the & means to take the address of that element. The essentially means you are making pnext point to a pointer to the next element.

---

The last line:

list1 = *pnext;

means that you taking the value pointed to by pnext and assigning it to list1.

---

list1 is of type Node* and pnext is of type Node** meaning it should hold the address of a variable whose type is Node*.

*pnext = list1;

When you dereference pnext, you get Node*. So, this assignment is correct.

pnext = &list1->next;

Here -> has a higher precedence over &. So, it returns a pointer's address( i.e., address of a Node* type )

list1 = *pnext;

This is just the opposite of the first statement. Dereferencing pnext gives Node* which can be assigned to list1.

---

Yes, you can change this( i.e., logically they does the same thing ) -

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

to

list1 = list1->next ;

But, you have a statement -

 *pnext = list2;

If pnext wasn't initialized as in the two step sequence, dereferencing an uninitialized pointer( i.e., *pnext ) would result segmentation fault. That is the reason.

---

Try to install visual studio express edition. Once you debug the program in VS-2012, you can simply hover the mouse on the pointer and it'll show you the contents by dereferencing the address.