-2

The following is my reverse linked list code. It is running in endless loop(on the second node i.e it continuously prints 2-> if the list is 1->2->3->4). Any help will be appreciated.

first is the head node pointer. Temp is the temporary node. Prev is the previous node.

The structure of the node is 

struct node {

     int num;
     struct node *ptr;
 } ;

The idea behind this approach is :- I will iteratively find the last node and print it. The prev node points to the node just before the temp node , which is the node that finally points to the last node before deleting it. The outer while loop terminates as soon as the first , which is the pointer to the first node of the list is the last node . Every time the else block of the outer while loop is executed. The prev and temp points to the next node after the first node.

The insertion of the linked list is working properly. I have already checked that part. I have also run through the entire code a couple of times and tried predicting each step but to no avail.

while (1)
{
    if (first->ptr == 0)
    {
        printf("%d\n",first->num);
        break;
    }
    else
    {
        temp = prev = first->ptr;
        while (1)
        {
            if (temp->ptr == 0)
            {

                printf("%d->", temp->num);
                temp = 0;
                prev->ptr = 0;
                break;
            }
            else
            {
                prev = temp->ptr;
                prev = temp;
                temp = temp->ptr; 
            }
        }
    }
}
abRao
  • 2,787
  • 1
  • 25
  • 37
Echo
  • 570
  • 1
  • 7
  • 21
  • The only place where you actually change the structure of the linked list is `prev->ptr = 0;`, so obviously that is not enough to reverse the list, all it does is remove a link. – interjay Sep 02 '15 at 14:01
  • Take a pen and a paper, and trace your code line by line. Also `prev = temp->ptr; prev = temp;` these two lines one after the other makes no sense, the first one is completely redundant. – Haris Sep 02 '15 at 14:02
  • A more complete discussion on this problem, https://stackoverflow.com/q/1801549/2472827. – Neil Jun 05 '18 at 01:26

2 Answers2

0
    ...
         prev->ptr = 0;
         break; 
     }
 }

This break stops inner loop, but not the outer one. For that happen: first->ptr == 0, use a return, other variable to keep control (some flag, like a int x = 0, if(!x)..) or even a goto.

hlscalon
  • 7,304
  • 4
  • 33
  • 40
0

Your code is quite ambiguous.

1) You have not given your structure definition here and that is why, first->ptr seems quite ambiguous to me. What does "ptr" refer to?

2) temp = prev = first->ptr;

first is a pointer to ListNode (I am assuming), then what does first->ptr mean? Tell about first->num too?

2) You have two while loops. You are breaking out of inner while, with some logic, but not out of outer while ,because to break out of outer while, you should have modified first->ptr in subsequent lines, which you are not doing.In no way, you will break out of outer while.

vvs14
  • 720
  • 8
  • 19
  • I have made the necessary changes. Sorry for the inconvenience. – Echo Sep 02 '15 at 15:27
  • My logic for the outer while loop termination is that , in the inner while loop the last node is deleted. So when the second node becomes the last node (after a number of iteration), it will get deleted. Hence, first->ptr will point to 0. Thus leading to the termination by break. I am not sure if it is working. Can you suggest some change which will lead to it working. I know I am asking a lot. Thank you for the help. – Echo Sep 03 '15 at 06:28
  • You will need only one iteration over List and few pointers (2 or 3). You also need to take care of condition that after reversing the List, `first` should point to original last node. – vvs14 Sep 03 '15 at 08:55