Question

How do you reverse a singly-linked list in C?

Answer 1

This is what my linked lists look like:

typedef struct {
int data;
struct NODE* next;
} NODE

Answer 2

I'm just starting to read about C and C++ with the intention of studying objective C further after those 2, I'll answer you when I'm done studying them :) jkjk lol, idk how to go about this, it's not similar to any of the code syntax i'm familiar with, have you checked google or any C forums?

Answer 3

it's alright... I just need the basic idea :-D

Answer 4

What exactly do you mean with "reverse"?

Answer 5

turn this:
[head]->...->[tail]
into this:
[head]<-...<-[tail]

so that the tail node is the new head

Answer 6

wait, so like if u have like an array with a list of variables, you make the list read backward?
say [0,1,2,3,4]
turns to
[4,3,2,1,0] ..... not sure what u mean by reverse tbh

Answer 7

Hm, have you tried anything of your own? (this is really elementary)

Answer 8

@sasogeek

right, but with a singly linked list instead of an array :-D

@ffm

This is the very first time I've done anything with linked lists. In fact, that definition of a node up there was the first time I tried implementing a linked list.

Answer 9

so I don't know what the -> operator in C does

Answer 10

I don't even know how to traverse a singly-linked list.

Answer 11

or insert/delete etc.

Answer 12

lol

Answer 13

Then learn traversing, inserting and deleting first.

Answer 14

I could use some pointers (get it? pointers! hahahaha)

Answer 15

Google is your friend ;)

Answer 16

I like http://rosettacode.org

Answer 17

I apologize for the delay; I had to make some drawings.

Answer 18

Alright here is my linked list traversal code:

void traverse_list(NODE* node)
{
for (;node->next; node = node->next);
}

Answer 19

Well, when it comes to programming, there are many ways to implement the same thing. In the spur of the moment, I came up with one way to accomplish this. Assume you have the attached linked-list.

Answer 20

That's a singly linked list :-D

Answer 21

The first step of my algorithm would be to access the very first element of the list, assign its pointer to a "helper" one, and set the pointer of the first link to null.

Answer 22

Sorry, OS issues.

Answer 23

So these are your first steps:

1. Define a temporary pointer variable, and assign it to the 'next' field of the head (i.e. have it point to the node after the head)
2. Set the 'next' field of the head to NULL

Now the head is lonely and the new head is the node pointed to by the temporary pointer variable.

Answer 24

Site is buggy :-D

Answer 25

My code looks like this now:
\[#
NODE* reverse_list(NODE* head)
{
NODE* temp;
temp = head->next;
head->next = NULL;
}
\]

Answer 26

The second step would be to set the pointer of the element the helper pointer points to to the head pointer (in this case, the first element), set the head pointer to the helper pointer, and move on to the next element with the helper pointer.

Answer 27

Recursion seem to be a good choice here.

Answer 28

The third step would be to repeat this process until your helper pointer reaches the null pointer, in which case you would have successfully reversed your linked-list.

Answer 29

@FFM

I think that's one property of singly-linked lists I should know; that something about them makes recursive solutions suitable for doing stuff with them or something,

Answer 30

An implementation of this algorithm would look something like this:

void reverse(NODE* head) {
NODE* helper = head->next;
head->next = NULL;
while (helper != NULL) {
helper->next = head;
head = helper;
helper = helper->next;
}
}

You'd have to double check, though, as I haven't even tested it.

Answer 31

i just got an infinite loop :(

Answer 32

Try and make sure your compiler understand what "NULL" means; it sometimes has a different name.

Answer 33

my compiler has it mean (void*) 0

Answer 34

http://ideone.com/rVSlr

Answer 35

http://ideone.com/Vj4uy I've found a working version! :-D

Answer 36

And I found a logical mistake in mine. :) Quick fix, though. I hope I helped in some way.

Answer 37

You did; thanks to you I finally understand singly linked lists... and the other types of lists are much easier to understand once you get the idea of singly-linked lists.

Answer 38

I'm no longer a loser who thinks linked lists == arrays!

Answer 39

haha

Answer 40

This may be too late to be of interest, but here it is....

Answer 41

Great recursive solution!

Answer 42

without recursion

/* reverse a linked list. return a pointer to the new first node */
nodetype* revnodes2(nodetype *p)
{
nodetype *prev,*pn;

if(p)
{
for(prev= (nodetype *)NULL,pn= p->next; pn; prev=p,p=pn,pn=pn->next)
p->next= prev;
p->next= prev;
}
return p;
}