C - I want to reverse a Linked List

Question

I want to reverse a linked list and my code doesn't seem to work. I don't know what is wrong with it. I used a reverse() function I found here, I even tested it on paper so I'm pretty sure the code is good but I must be missing something still. I'd love to find out what is wrong. Here is my code:

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


typedef struct node{
    int val;
    struct node * next;
}node;

void push(int val, node **head){
    node* temp=(node*)malloc(sizeof(node));
    node* current=*head;
    temp->val=val;
    if(*head==NULL)
        {*head=temp;
        temp->next=NULL;}
    else
        {while(current->next!=NULL)
            current=current->next;
    current->next=temp;
    temp->next=NULL;}
 }
int reverse(node * head){
   node *previous = NULL;
   node *current = head;
   node *forward;
   while (current != NULL) {
       forward = current->next;
       current->next = previous;
       previous = current;
       current = forward;
      }
    return previous;

   }
 void print(node *new_head){

    node* current2=new_head;
    current2=current2->next;
    while(current2!=NULL)
     {
       printf("%d", current2->val);
       current2=current2->next;
      }}

int main()
{   node * head= NULL;
    int n;
    node * new_head;
    scanf("%d", &n);
    push(n,head);
    scanf("%d", &n);
    push(n,head);
    scanf("%d", &n);
    push(n,head);
    new_head=reverse(head);
    print(new_head);

    return 0;}

I just want to reverse an input like: 1,2,3. So the output would be 3,2,1.

Your push is strange. I would expect push to add node before the current head, not at the end of the list (it would be also much cheaper, performance-wise). — Ashalynd, Nov 01 '14 at 18:38
@Ashalynd I just barely started understanding linked lists and I know most of what I wrote is pretty weird/inneficient. — Ryncops, Nov 01 '14 at 18:41
`void push(int val, node **head){` push() expects a pointer to pointer as 2nd argument. `node * head= NULL; push(n,head);` but you are giving it a pointer. — wildplasser, Nov 01 '14 at 18:41

score 0 · Answer 1 · answered Nov 01 '14 at 18:40

Actually, your reverse is working. It's the push method that doesn't work according to spec: it moves the new element to the end of your list, instead of before the current head. So you already have the reversed list before the call to your reverse method (which promptly reverses it the other way round).

score 0 · Answer 2 · answered Nov 01 '14 at 18:57

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

typedef struct node{
    int val;
    struct node * next;
}node;

void push(int val, node **head){
    node* temp=(node*)malloc(sizeof(node));
    node* current=*head;

    temp->val=val;
    temp->next=NULL;
    if(*head==NULL){
        *head=temp;
    } else {
        while(current->next!=NULL)
            current=current->next;
        current->next=temp;
    }
}
node *reverse(node * head){
    node *rev = NULL;
    node *current = head;
    node *temp;

    while (current != NULL) {
        temp = current->next;
        current->next =rev;
        rev = current;
        current = temp;
    }
    return rev;
}
void print(node *new_head){
    node* current2=new_head;
    while(current2!=NULL){
        printf("%d ", current2->val);
        current2=current2->next;
    }
    printf("\n");
}

int main(){
    int n;
    node * head= NULL;
    node * new_head;
    scanf("%d", &n);
    push(n, &head);
    scanf("%d", &n);
    push(n, &head);
    scanf("%d", &n);
    push(n, &head);
    //print(head);
    new_head=reverse(head);
    print(new_head);

    return 0;
}

4pie0 · Answer 3 · 2014-11-01T19:20:12.937

0

push( n, &head); is what you have to do in order to pass head pointer by pointer. Otherwise in push method node* current=*head; will result in segmentation fault as you are passing null pointer itself instead of pointer to it.

edited Nov 01 '14 at 19:20

answered Nov 01 '14 at 19:12

4pie0

29,204
9
82
118

score 0 · Accepted Answer · answered Nov 01 '14 at 19:19

Try the following

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

typedef struct node
{
    int val;
    struct node * next;
} node;

void push( node **head, int val )
{
    node **current = head;

    while ( *current ) current = &( *current )->next;

    *current = ( node * )malloc( sizeof( node ) );

    ( *current )->val  = val;
    ( *current )->next = NULL;
}

node * reverse( node * head )
{
    node *new_head = NULL;
    node *current = head;

    while ( current ) 
    {
        node *next = current->next;
        current->next = new_head;
        new_head = current;
        current = next;
    }

    return new_head;
}

void print( const node *head )
{
    for ( ; head; head = head->next ) printf( "%d ", head->val );
    printf( "\n" );
}

void delete( node *head )
{
    while ( head )
    {
        node *tmp = head;
        head = head->next;
        free( tmp );
    }
}

int main()
{   
    node *head = NULL;
    int n;

    scanf( "%d", &n );
    push( &head, n );

    scanf( "%d", &n );
    push( &head, n );

    scanf( "%d", &n );
    push( &head, n );

    print( head );

    head = reverse( head );

    print( head );

    delete( head );

    return 0;
}

If to enter 1 2 3 the output will be

1 2 3 
3 2 1

C - I want to reverse a Linked List

4 Answers4