Tracing through Linked List code

Question

Here is a linked list where pList points to the node containing the value 3

pList
  |
  3       7       6       1       2       8       4      5    ->     NULL

Given the following code, redraw the list showing the changes to the list after the following code is executed.

pCur = pList;
while(pCur->next->next != NULL)
   pCur = pCur->next;
pCur->next->next = pList;
pList = pCur -> next;
pCur -> next = NULL;
pCur = NULL;

Here is my interpretation of what is happening: pCur = pList (pCur = pList) | 3 7 6 1 2 8 4 5 -> NULL

pList    pCur  (pCur = pCur->next)
  |       |
  3       7       6       1       2       8       4      5    ->     NULL

         pCur           PList (pCur->next->next = pList)
          |               |
  3       7       6       1       2       8       4      5    ->     NULL

         pCur   pList       (pList = pCur->next)
          |       |
  3       7       6       1       2       8       4      5    ->     NULL


                     (pCur->next = NULL)
  3       7       6       1       2       8    -> NULL

I don't believe this is correct. What am I doing wrong?

I don't know whether that's right or not. If you don't believe that you have it correct, you could always step through it in a debugger, to see what it actually does. — Oliver Charlesworth
– Oliver Charlesworth, Commented Jan 23, 2011 at 18:20

Sebastian Paaske Tørholm · Accepted Answer · 2011-01-23 18:35:18Z

What it actually does is this:

We start with the following:

pCur = pList (pCur = pList)
  |
  3       7       6       1       2       8       4      5    ->     NULL

We then move pCur one forward while pCur->next->next != NULL, so we end up with

pList                                           pCur
  |                                               |
  3       7       6       1       2       8       4      5    ->     NULL

Then we attach the head of the list to the tail

pList                                           pCur          pList (again)
  |                                               |             |
  3       7       6       1       2       8       4      5      3      7 ....

This gives us an infinitely circular list.

We then move pList to point to pCur->next

                                                pCur   pList      
                                                  |      |       
  3       7       6       1       2       8       4      5      3      7 ....

If we move this over so that pList is first (which we can do, as it's infinitely circular):

pList                                                   pCur   pList (again)
  |                                                       |      | 
  5       3       7       6       1       2       8       4      5      3      7 ....

We finally say that what follows pCur is NULL, giving us:

pList                                                   pCur   
  |                                                       |      
  5       3       7       6       1       2       8       4    ->     NULL

As you can see, what this does is move the last element of the list up to the front.

Fred Foo · Accepted Answer · 2011-01-23 18:27:03Z

0

You're omitting the links, so you can't show the effect of pCur->next = NULL. Also, pCur->next->next = pList sets pCur, not pList.

It's pretty easy to make these drawing programmatically:

void print_list(Link const *pCur, Link const *pList)
{
    Link const *p;

    printf("pCur -> ");
    for (p = pCur; p != NULL && p != pList; p = p->next)
        printf("%d -> ", p->data);
    puts(p == NULL ? "NULL" : "pList");

    printf("pList -> ");
    for (p = pList; p != NULL && p != pCur; p = p->next)
        printf("%d -> ", p->data);
    puts(p == NULL ? "NULL" : "pCur");
}

edited Jan 23, 2011 at 18:27

answered Jan 23, 2011 at 18:20

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Collectives™ on Stack Overflow

Tracing through Linked List code

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related