invert singly linked list

2 views
Skip to first unread message

T. Ment

unread,
Dec 21, 2019, 12:17:15 PM12/21/19
to
Some people say "reverse" but "invert" seems apt to me.

The simplest list is LIFO. You only need one pointer, the tail, and you
always insert there. That's fine for a stack.

But what about FIFO order from the same list? Can you invert it?

Yes, and Youtube has videos with code. But I chose variable names that
make their purpose clearer to me. So here's my version:



# include <stdio.h>
# include <stdlib.h>

struct NODE {
struct NODE *next;
char data[1];
};

void
print (struct NODE *node)
{
while (node) {
printf ("node %d\n", node->data[0]);
node = node->next;
}
}

void
invert (struct NODE *&node)
{
struct NODE *next, *swap; /* next=old swap=new */

if (!node)
return;

swap = 0;
while (node) {
next = node->next;
node->next = swap;
swap = node;
node = next;
}
node = swap;
}

void
main ()
{
struct NODE *node = 0, *next;

for (int i = 0; i < 4; i++) {
next = node;
node = (struct NODE *) malloc (sizeof (struct NODE));
if (!node) {
fprintf (stderr, "failure allocating node memory\n");
exit (1);
}
node->next = next;
node->data[0] = (char) i;
}

print (node);
printf ("\n");

invert (node);
print (node);
printf ("\n");

invert (node);
print (node);
}

Reply all
Reply to author
Forward
0 new messages