Create a Reverse Linkedlist in C++ from a Given Linkedlist

Create a reverse LinkedList in C++ from a given LinkedList

Easier one: Go through your linked list, save the previous and the next node and just let the current node point at the previous one:

void LinkedList::reversedLinkedList()
{
    if(head == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = head;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    head = prev;
}

What is the best way to create/reverse a linked list?

The best way to reverse a singly-linked list is to reverse it without invoking undefined behavior

In your function reversedList you do not check whether the passed pointer curr is equal to NULL. So the expression in the while loop

while(curr->next != NULL)

can invoke undefined behavior.

The function can be defined the following way

node * reversedList( node *head )
{
    // a->b->c->d
    // d->c->b->a

    node *curr = head;
    head = NULL;

    while ( curr != NULL )
    {
        Node *tmp = curr;
        curr = curr->next;
        tmp->next = head;
        head = tmp; 
    }

    return head;
}

Pay attention to that the parameter of the recursive function printList should be declared with the qualifier const because the list is not changed within the function

void printList(cosnt node *head);

I would declare and define the recursive function the following way

FILE * printList( const node *head, FILE *fp )
{
    if ( head )
    {
        fprintf( fp, "%d ", head->number );
    
        printList( head->next, fp );
    }

    return fp;
}

and in main you could write

fputc( '\n', printList( head, stdout ) );

Using such a function you could output the list in any stream including a file stream.

How to reverse a linked list in pairs

what is wrong in my code.

The main problem I see is here:

            prev->next = temp;

On the first iteration of the loop, prev is still NULL at that point, so you're performing a null-pointer dereference.

You can resolve that issue and also remove the special case for the list head by introducing a synthetic head node in front of the real nodes:

ListNode* reverseListInPairs(ListNode *head) {
    ListNode fake_head = { .next = head };
    ListNode *prev = &fake_head;
    ListNode *current = head;

    while (current != NULL && current->next != NULL) {
        ListNode *temp = current->next;

        current->next = current->next->next;
        temp->next = current;
        prev->next = temp;

        prev = current;
        current = current->next;
    }

    return fake_head.next;
}

I've stuck as close as possible to your original code there, but personally, I'd tighten it up a little further. In particular, you don't need to maintain both current and prev across iterations; just the latter would be sufficient.

ListNode* reverseListInPairs(ListNode *head) {
    ListNode fake_head = { .next = head };
    ListNode *prev = &fake_head;

    while (prev->next && prev->next->next) {
        ListNode *first = prev->next;
        ListNode *second = first->next;

        prev->next = second;
        first->next = second->next;
        second->next = first;

        prev = first;
    }

    return fake_head.next;
}

How to reverse a linked list implementation of a queue

First of all, you have a problem in this line:

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

As you shadow the type node by the pointer with the same name, the argument given to sizeof is wrong. Use a different variable name in that function.

Also, in C it is considered better not to cast what malloc returns:

    node *curnode = malloc(sizeof(node));
    // ...use curnode below ...

The reverse function

The problem is with this line:

q->head = node;

As you have just reversed the queue that starts at node->next, node->next will now be the tail of the queue, so when you do the above assignment, you limit the queue to two elements, and lose the reference to the other nodes.

As a solution, don't use a second function argument, nor next references. Just dequeue - recurse - and enqueue again:

void reverse(queue *q)
{
    if (empty(q))
        return;
    int tmp = dequeue(q);
    reverse(q);
    enqueue(q, tmp);
}

Reverse a linked list after a given value, without creating new nodes

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

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

void reverse(Node **head){
    Node *tmp, *list, *newList = NULL;
    if (head==NULL || *head == NULL) return;
    list = *head;
    while(list != NULL){
        tmp = list;
        list = list->next;
        tmp->next = newList;
        newList = tmp;
    }
    *head = newList;
}

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

void reverseAfter(Node *head, int val){
    //The first element excluded
    if(head == NULL) return ;

    while(head->next && head->next->val != val)
        head = head->next;
    reverse(&head->next);
}

int main(void){
    Node *head;
    Node n[6] = {
        {1,NULL}, {2, NULL}, {3, NULL},
        {4,NULL}, {5, NULL}, {6, NULL}
    };
    n[0].next = &n[1];n[1].next = &n[2];n[2].next = &n[3];
    n[3].next = &n[4];n[4].next = &n[5];

    head = &n[0];
    print(head);//1 2 3 4 5 6
    //reverse(&head);
    reverseAfter(head, 4);
    print(head);//1 2 3 6 5 4
    return 0;
}

Reversing a Linked List not working in C. Only giving the top element

Your Reverse function works perfectly well.

Your will laugh, because your mistake is really silly : you use the wrong parameter for your function.
Now that your list is reversed, head is the new tail and it points to NULL.

Call your function like that :

LinkedListTraversal(head);
Reverse(head);
cout << "------------------\n";
LinkedListTraversal(third);

---

Related Topics