XOR linked list: Reverse last K nodes of a Linked List
Given a XOR Linked List and a positive integer K, the task is to reverse the last K nodes in the given XOR linked list.
Examples:
Input: LL: 7 <–> 6 <–> 8 <–> 11 <–> 3 <–> 1, K = 3
Output: 7<–>6<–>8<–>1<–>3<–>11Input: LL: 7 <–> 6 <–> 8 <–> 11 <–> 3 <–> 1 <–> 2 <–> 0, K = 5
Output: 7<–>6<–>8<–>0<–>2<–>1<–>3<–>11
Approach: Follow the steps below to solve the given problem:
- Reverse the given XOR Linked List.
- Now, reverse the first K nodes of the reversed linked list.
- After completing the above steps, reverse the linked list again to get the resultant linked list.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Structure of a node of XOR Linked Liststruct Node { // Stores data value of a node int data; // Stores XOR of previous pointer and next pointer struct Node* nxp;};// Function to calculate Bitwise XOR of the two nodesstruct Node* XOR(struct Node* a, struct Node* b) { return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));}// Function to insert a node with given value at given positionstruct Node* insert(struct Node** head, int value) { // If XOR linked list is empty if (*head == NULL) { // Initialize a new Node struct Node* node = new Node; // Stores data value in the node node->data = value; // Stores XOR of previous and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If the XOR linked list is not empty else { // Stores the address of the current node struct Node* curr = *head; // Stores the address of the previous node struct Node* prev = NULL; // Initialize a new Node struct Node* node = new Node; // Update address of current node curr->nxp = XOR(node, XOR(NULL, curr->nxp)); // Update address of the new node node->nxp = XOR(NULL, curr); // Update the head node *head = node; // Update the data value of current node node->data = value; } return *head;}// Function to print elements of the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer in the current node struct Node* curr = *head; // Stores XOR pointer in the previous Node struct Node* prev = NULL; // Stores XOR pointer in the next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print the current node std::cout << curr->data << " "; // Forward traversal next = XOR(prev, curr->nxp); // Update the prev pointer prev = curr; // Update the curr pointer curr = next; }}// Function to reverse the linked list in the groups of Kstruct Node* reverseK(struct Node** head, int K, int len) { struct Node* curr = *head; // If head is NULL if (curr == NULL) return NULL; // If the size of XOR linked list is less than K else if (len < K) return *head; else { int count = 0; // Stores the XOR pointer in the previous Node struct Node* prev = NULL; // Stores the XOR pointer in the next node struct Node* next; while (count < K) { // Forward traversal next = XOR(prev, curr->nxp); // Update the prev pointer prev = curr; // Update the curr pointer curr = next; // Count the number of nodes processed count++; } // Remove the prev node from the next node prev->nxp = XOR(NULL, XOR(prev->nxp, curr)); // Add the head pointer with prev (*head)->nxp = XOR(XOR(NULL, (*head)->nxp), curr); // Add the prev with the head if (curr != NULL) curr->nxp = XOR(XOR(curr->nxp, prev), *head); return prev; }}// Function to reverse last K nodes of the given XOR Linked Listvoid reverseLL(struct Node* head, int N, int K) { // Reverse the given XOR LL head = reverseK(&head, N, N); // Reverse the first K nodes of // the XOR LL head = reverseK(&head, K, N); // Reverse the given XOR LL head = reverseK(&head, N, N); // Print the final linked list printList(&head);}// Driver Codeint main(){ // Stores number of nodes int N = 6; // Given XOR Linked List 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);}// This code is contributed by ajaymakvana. |
C
// C program for the above approach#include <inttypes.h>#include <stdio.h>#include <stdlib.h>// Structure of a node// of XOR Linked Liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};// Function to calculate// Bitwise XOR of the two nodesstruct Node* XOR(struct Node* a, struct Node* b){ return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));}// Function to insert a node with// given value at given positionstruct Node* insert(struct Node** head, int value){ // If XOR linked list is empty if (*head == NULL) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores data value in the node node->data = value; // Stores XOR of previous // and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If the XOR linked // list is not empty else { // Stores the address // of the current node struct Node* curr = *head; // Stores the address // of the previous node struct Node* prev = NULL; // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Update address of current node curr->nxp = XOR(node, XOR( NULL, curr->nxp)); // Update address of the new node node->nxp = XOR(NULL, curr); // Update the head node *head = node; // Update the data // value of current node node->data = value; } return *head;}// Function to print elements// of the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer // in the current node struct Node* curr = *head; // Stores XOR pointer // in the previous Node struct Node* prev = NULL; // Stores XOR pointer in the // next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print the current node printf("%d ", curr->data); // Forward traversal next = XOR(prev, curr->nxp); // Update the prev pointer prev = curr; // Update the curr pointer curr = next; }}// Function to reverse the linked// list in the groups of Kstruct Node* reverseK(struct Node** head, int K, int len){ struct Node* curr = *head; // If head is NULL if (curr == NULL) return NULL; // If the size of XOR linked // list is less than K else if (len < K) return *head; else { int count = 0; // Stores the XOR pointer // in the previous Node struct Node* prev = NULL; // Stores the XOR pointer // in the next node struct Node* next; while (count < K) { // Forward traversal next = XOR(prev, curr->nxp); // Update the prev pointer prev = curr; // Update the curr pointer curr = next; // Count the number of // nodes processed count++; } // Remove the prev node // from the next node prev->nxp = XOR(NULL, XOR(prev->nxp, curr)); // Add the head pointer with prev (*head)->nxp = XOR(XOR(NULL, (*head)->nxp), curr); // Add the prev with the head if (curr != NULL) curr->nxp = XOR(XOR(curr->nxp, prev), *head); return prev; }}// Function to reverse last K nodes// of the given XOR Linked Listvoid reverseLL(struct Node* head, int N, int K){ // Reverse the given XOR LL head = reverseK(&head, N, N); // Reverse the first K nodes of // the XOR LL head = reverseK(&head, K, N); // Reverse the given XOR LL head = reverseK(&head, N, N); // Print the final linked list printList(&head);}// Driver Codeint main(){ // Stores number of nodes int N = 6; // Given XOR Linked List 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);} |
Output:
7 6 8 1 3 11
Time Complexity: O(N), as we are using a loop to traverse N times, where N is the length of the linked list.
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
