How to reverse the link list i have created in C

Question

I have created a linked list but couldn't think of how to reverse the same. I know the algo but i think i have made a mistake in creating the list. What could be the change in reverse function so that it work. Following is the code:

typedef struct Node{
    int data;
    struct Node* next;
} node;
node* head;
int count;
void insertAtBegin(int value){
    if(head==NULL){
        head = (node*)malloc(sizeof(node));
        head->data = 0;
        head->next = NULL;
    }
    node* newNode = (node*)malloc(sizeof(node));
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
    count++;
}

void display(){
    node* temp = (node*)malloc(sizeof(node));
    temp = head;
    while(temp->next!=NULL){
        printf("%d\t",temp->next->data);
        temp = temp->next;
    }
    printf("\n");
}

void reverse(){
    node *p, *q, *r;

    p = q = r = head;
    p = p->next->next;
    q = q->next;
    r->next = NULL;
    q->next = r;

    while (p != NULL){
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    head = q;
}

void main(){
    insertAtBegin(5);
    insertAtBegin(6);
    display();
    reverse();
    display();
    printf("\nSize of linked list is %d",count);
}

`node* temp = (node*)malloc(sizeof(node)); temp = head;` is a memory leak. Why do you alloc a node when you want to display them? — mch, Sep 29 '16 at 15:11
Start coding yourself and then ask questions if you have difficulties. — Jabberwocky, Sep 29 '16 at 15:13
@mch ok i didn't have the idea..thanks but that would probably not solve my problem of reversing... — Saurav Suman, Sep 29 '16 at 15:14

score 2 · Accepted Answer · edited May 23 '17 at 12:33

Let's say you have the following list:

head = n0
n0 -> ... -> A -> B -> C -> D -> E -> ... -> nN -> NULL

That you want to reverse to:

head = nN
nN -> ... -> E -> D -> C -> B -> A -> ... -> n0 -> NULL

Now, let's consider the case when the beginning of the list is already reversed and that you're dealing with the node C. Your list at that time is:

head = B
B -> A -> ... -> n0-> NULL
tmpHead  = C
C -> D -> E ... -> nN -> NULL

Where tmpHead is a temporary variable that allow you to not lose a reference to C (as B.next is now pointing to A) You want to:

connect B to C so that B comes after C
Set head to C, the new head of the reversed list
keep D in the temporary variable tmpHead, so that you can still access it

Reversing then becomes:

node * tmp   = tmpHead.next;  // 3. part 1
tmpHead.next = head;          // 1.
head         = tmpHead;       // 2.
tmpHead      = tmp;           // 3. part 2

The stop condition is quite obvious: you have to stop when you reached the end of the list, so, when tmpHead is NULL. As to the initialization, as head as to point to the reversed part and tmpHead to the non reversed one. So tmpHead has to be set to head and head to NULL.

At the end, you get the following function which take a pointer to the first node of your list as input parameter

void reverse(node ** head)
{
  node * tmpHead = (* head);
  (* head)       = NULL;

  while(tmpHead)
  {
    node * tmp    = tmpHead->next;
    tmpHead->next = (* head);
    (* head)      = tmpHead;
    tmpHead       = tmp;
  }
}

Note that there's a "problem" with the way you insert a new node at the beginning of your list : you always keep a "phantom" node with data set to 0 and that you call head. So, the first real node of the list, as I defined it, is your head->next. Which means you have to call the reverse function like this : reverse(& (head->next)) or slightly modify the function.

Also, please note that you shouldn't cast the result of a malloc. Do I cast the result of malloc?

I think you need to replace `head` with `*head` throughout the body of your `reverse` function. — Ian Abbott, Sep 29 '16 at 16:51

How to reverse the link list i have created in C

1 Answers1