to reverse a linked list

Question

I am a beginner and was trying to reverse a linked list so here i wrote a function to reverse a linked list.

void reverse_list(struct node **head_ref)
{
    struct node *temp = *head_ref;
    if(temp == NULL)
        return;
    else if(temp->next == NULL)
        return;
    else
    {
        struct node *temp_r = temp;
        int count = count_list(temp); // no.of nodes in the list
        while(temp != NULL)
        {
            struct node *temp_t = temp_r;
            int i;
            for(i=0;i<count;i++)
            {
                if(i!=0)
                    temp_t = temp_t->next;   // loop to find the node which is to be swapped with temp
            }
            if(temp_t == temp)    // base condition to stop swapping
                return;
            else
            {
                swap_node(&temp_r,temp->data,temp_t->data);
            }
            temp = temp->next; // traverse through the list
            count--; 
        }
    }
}

logic i used: i want to reverse the linked list by swapping the node in this way (1,n) ,(2,n-1),(3,n-3) ..

but when i execute this code it only prints the first element of the list.

After running debugger i understood that i made two copies of the original list and i was actually swapping the nodes of two different list which is not possible by the function swap_node() defined in the code, here is the swap_node() function

void swap_node(struct node **head_ref,int key1,int key2) // function to swap two nodes.
{
    if(key1==key2)
        return;
    // search for key1
    struct node *prevx = NULL, *currx = *head_ref;
    while(currx && currx->data != key1)
    {
        prevx = currx;
        currx = currx->next;
    }
    //search for key2
    struct node *prevy = NULL, *curry = *head_ref;
    while(curry && curry->data!=key2)
    {
        prevy = curry;
        curry = curry->next;
    }
    // if key1 or key2 are not present in the list
    if(currx == NULL || curry == NULL)
        return;
    // check if key1 is not head of the list
    if(prevx != NULL)
        prevx->next = curry;
    else
        *head_ref = curry; // then make key2 the head

    // check if key2 is not head of the list
    if(prevy != NULL)
        prevy->next = currx;
    else
        *head_ref = currx; // then make key2 the head

    // swapping the next pointers of the nodes
    struct node *temp = curry->next;
    curry->next = currx->next;
    currx->next = temp;

}

i want to reverse the linked list using the above logic but i am unable to do that , so please someone help me out to achieve this, how can i improve this code and how to proceed .

thanxs in advance.

Answer 1

your problem is within the while loop:

you don't need the number of nodes, because the while knows to traverse through the list.

Also, as you already knew, there should be 3 pointers (previous, current and next).

So your code end up looking like this:

void reverse_list(struct node **head_ref) {
    if(*head_ref == NULL || (*head_ref)->next == NULL)
        return;

    struct node *temp = *head_ref;
    struct node *next = NULL;
    struct node *pre = NULL;

    while(temp != NULL)
    {
        next = temp->next;
        temp->next = pre;
        pre = temp;
        temp = next;    
    }
    *head_ref = pre;
}

notice how you update the (original) head of the list to point at the reversed one.

Answer 2

Actually, the algorithm you use is too complex for reversing a linked list.

while(currx && currx->data != key1)
{//btw, these code may cause bugs if there are some same value in the linked list
    prevx = currx;
    currx = currx->next;
}

The code above shows that you do not really understand the essence of a linked list, in these code , you just process a linked list like it is a array. That will make your code run very slowly and should be avoided.

A better and faster way to reverse a linked list is like this :

struct Node
{
    int dataa;
    struct Node* next;
};
typedef struct Node* node;//some definition
node head = NULL;//global variables is not recommended in writing code ,but here it just make the code easier to read .

//Here you should do something to create the linked list

//eg: the linked list is 1 2 3 4 5 now ,the head pointer points at 1
void reverse(void)
{
    if (head != NULL)
    {
        node temp1 = head->next;
        node temp2 = head->next;
        head->next = NULL;
        while (temp2 != NULL)
        {
            temp2 = temp2->next;
            temp1->next = head;
            head = temp1;
            temp1 = temp2;
        }
    }
}
//now it will be 5 4 3 2 1 ,the head pointer points at 5

Just reverse the list from head to tail, one by one.