XOR linked list: Reverse last K nodes of a Linked List

  

#include <inttypes.h>

#include <stdio.h>

#include <stdlib.h>

  

struct Node {

  

    

    

    int data;

  

    

    

    struct Node* nxp;

};

  

struct Node* XOR(struct Node* a,

                 struct Node* b)

{

    return (struct Node*)((uintptr_t)(a)

                          ^ (uintptr_t)(b));

}

  

struct Node* insert(struct Node** head,

                    int value)

{

    

    if (*head == NULL) {

  

        

        struct Node* node

            = (struct Node*)malloc(

                sizeof(struct Node));

  

        

        node->data = value;

  

        

        

        node->nxp = XOR(NULL, NULL);

  

        

        *head = node;

    }

  

    

    

    else {

  

        

        

        struct Node* curr = *head;

  

        

        

        struct Node* prev = NULL;

  

        

        struct Node* node

            = (struct Node*)malloc(

                sizeof(struct Node));

  

        

        curr->nxp = XOR(node,

                        XOR(

                            NULL, curr->nxp));

  

        

        node->nxp = XOR(NULL, curr);

  

        

        *head = node;

  

        

        

        node->data = value;

    }

    return *head;

}

  

void printList(struct Node** head)

{

    

    

    struct Node* curr = *head;

  

    

    

    struct Node* prev = NULL;

  

    

    

    struct Node* next;

  

    

    while (curr != NULL) {

  

        

        printf("%d ", curr->data);

  

        

        next = XOR(prev, curr->nxp);

  

        

        prev = curr;

  

        

        curr = next;

    }

}

  

struct Node* reverseK(struct Node** head,

                      int K, int len)

{

    struct Node* curr = *head;

  

    

    if (curr == NULL)

        return NULL;

  

    

    

    else if (len < K)

        return *head;

    else {

  

        int count = 0;

  

        

        

        struct Node* prev = NULL;

  

        

        

        struct Node* next;

  

        while (count < K) {

  

            

            next = XOR(prev, curr->nxp);

  

            

            prev = curr;

  

            

            curr = next;

  

            

            

            count++;

        }

  

        

        

        prev->nxp = XOR(NULL,

                        XOR(prev->nxp,

                            curr));

  

        

        (*head)->nxp = XOR(XOR(NULL,

                               (*head)->nxp),

                           curr);

  

        

        if (curr != NULL)

            curr->nxp = XOR(XOR(curr->nxp,

                                prev),

                            *head);

        return prev;

    }

}

  

void reverseLL(struct Node* head,

               int N, int K)

{

  

    

    head = reverseK(&head, N, N);

  

    

    

    head = reverseK(&head, K, N);

  

    

    head = reverseK(&head, N, N);

  

    

    printList(&head);

}

  

int main()

{

    

    int N = 6;

  

    

  

    struct Node* head = NULL;

    insert(&head, 1);

    insert(&head, 3);

    insert(&head, 11);

    insert(&head, 8);

    insert(&head, 6);

    insert(&head, 7);

  

    int K = 3;

  

    reverseLL(head, N, K);

  

    return (0);

}

Let's block ads! (Why?)