Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सिंगली लिंक्ड लिस्ट में वैकल्पिक K नोड्स को उल्टा करें


इस ट्यूटोरियल में, हमें लंबाई N की एक लिंक्ड लिस्ट A और एक पूर्णांक K दिया गया है। हमें K आकार के प्रत्येक जोड़े के साथ नोड्स के वैकल्पिक जोड़े को उल्टा करना होगा। यह भी दिया गया है कि N, K से विभाज्य है। पहला तर्क लिंक्ड लिस्ट A का हेड पॉइंटर है और दूसरा तर्क एक पूर्णांक K है, उदाहरण के लिए

इनपुट

5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2

आउटपुट

6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3

आउटपुट

5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null

समाधान खोजने का दृष्टिकोण

पुनरावृत्त समाधान

  • प्रति पुनरावृत्ति (या लूप) 2K नोड्स पार करें और दिए गए इनपुट (लिंक्ड लिस्ट) में K नोड्स के प्रत्येक जोड़े के हेड और टेल को जॉइन और टेल पॉइंटर का उपयोग करके रिकॉर्ड करें।

  • फिर, लिंक्ड लिस्ट के K नोड्स को उल्टा करें और उल्टी लिस्ट के टेल नोड को, जॉइन पॉइंटर द्वारा इंगित प्रारंभिक लिंक्ड लिस्ट के हेड नोड के साथ जोड़ें।

  • फिर हम वर्तमान पॉइंटर को अगले K नोड्स पर बदल देंगे।

  • सामान्य लिस्ट का टेल अब अंतिम नोड के रूप में कार्य करता है (जिसे नए टेल द्वारा इंगित किया जाता है), और जॉइन पॉइंटर नई (उल्टी) लिस्ट के हेड की ओर इशारा करेगा, और उन्हें मर्ज किया जाता है। हम इन चरणों को तब तक दोहराएंगे जब तक सभी नोड्स समान चरणों का पालन नहीं करते।

उदाहरण

#include <bits/stdc++.h> using namespace std; class Node {    public:    int data;    Node* next; }; Node* kAltReverse(struct Node* head, int k){    Node* prev = NULL;    Node* curr = head;    Node* temp = NULL;    Node* tail = NULL;    Node* newHead = NULL;    Node* join = NULL;    int t = 0;    while (curr) {       t = k;       join = curr;       prev = NULL;       while (curr && t--) {          temp = curr->next;          curr->next = prev;          prev = curr;          curr = temp;       }       if (!newHead)          newHead = prev;       if (tail)          tail->next = prev;       tail = join;       tail->next = curr;       t = k;       while (curr && t--) {          prev = curr;          curr = curr->next;       }       tail = prev;    }    return newHead; } void push(Node** head_ref, int new_data){    Node* new_node = new Node();    new_node->data = new_data;    new_node->next = (*head_ref);    (*head_ref) = new_node; } void printList(Node* node){    int count = 0;    while (node != NULL) {       cout << node->data << " ";       node = node->next;       count++;    } } int main(void){    Node* head = NULL;    int i;    for (i = 6; i <27; i+=3)       push(&head, i);    int k = 3;    cout << "Given linked list \n";    printList(head);    head = kAltReverse(head, k);    cout << "\n Modified Linked list \n";    printList(head);    return (0); }

आउटपुट

Given linked list 24 21 18 15 12 9 6 Modified Linked list 18 21 24 15 12 9 6

पुनरावर्ती समाधान

  • शुरुआत से K नोड्स पार करें और टेम्प मान को k+1वें नोड पर सेट करें

  • पार किए गए सभी K नोड्स को उल्टा करें।

  • उस जोड़े के अंतिम नोड के नेक्स्ट पॉइंटर को टेम्प पर सेट करें।

  • अगली पुनरावृत्ति को छोड़ दें जिसमें उन K नोड्स के जोड़े को छोड़ना है।

  • अंतिम नोड तक पहुंचने तक अगले K नोड्स को उल्टा करने के लिए इन सभी चरणों को पुनरावर्ती रूप से पालन करें।

स्यूडो कोड

reverseAltK(head, k)   curr = head   prev = null   next = null   count = 0   WHILE count < k AND curr     next = curr.next     curr.next = prev     prev = curr     curr = next     count = count + 1 IF head     head.next = curr count = 0 WHILE count < k-1 AND curr     curr = curr.next     count = count + 1 IF curr     curr.next = reverseKGroupAltRecursive(curr.next, k) return prev

उदाहरण

#include <bits/stdc++.h> using namespace std; /* Link list node */ class node{    public:    int data;    node* next; }; /* Helper function for kAltReverse() */ node * _kAltReverse(node *node, int k, bool b); /* Alternatively reverses the given linked list in groups of given size k. */ node *kAltReverse(node *head, int k){    return _kAltReverse(head, k, true); } /* Helper function for kAltReverse(). It reverses k nodes of the list only if the third parameter b is passed as true, otherwise moves the pointer k nodes ahead and recursively calls iteself */ node * _kAltReverse(node *Node, int k, bool b){    if(Node == NULL)       return NULL;    int count = 1;    node *prev = NULL;    node *current = Node;    node *next;    /* The loop serves two purposes   1) If b is true,     then it reverses the k nodes   2) If b is false,     then it moves the current pointer */    while(current != NULL && count <= k){       next = current->next;       /* Reverse the nodes only if b is true*/          if(b == true)             current->next = prev;       prev = current;       current = next;       count++;    }    /* 3) If b is true, then node is the kth node.     So attach rest of the list after node.     4) After attaching, return the new head */    if(b == true){       Node->next = _kAltReverse(current, k, !b);       return prev;    }    /* If b is not true, then attach     rest of the list after prev.     So attach rest of the list after prev */    else{       prev->next = _kAltReverse(current, k, !b);       return Node;    } } /* UTILITY FUNCTIONS */ /* Function to push a node */ void push(node** head_ref, int new_data){    /* allocate node */    node* new_node = new node();    /* put in the data */    new_node->data = new_data;    /* link the old list off the new node */    new_node->next = (*head_ref);    /* move the head to point to the new node */    (*head_ref) = new_node; } /* Function to print linked list */ void printList(node *node){    int count = 0;    while(node != NULL){       cout << node->data << " ";       node = node->next;       count++;    } } // Driver Code int main(void){    /* Start with the empty list */    node* head = NULL;    int i;    // create a list 1->2->3->4->5...... ->20    for(i = 20; i > 0; i--)       push(&head, i);    cout << "Given linked list \n";    printList(head);    head = kAltReverse(head, 3);    cout << "\nModified Linked list \n";    printList(head);    return(0); }

आउटपुट

Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

निष्कर्ष

इस ट्यूटोरियल ने हमें सिखाया कि सिंगली लिंक्ड लिस्ट में वैकल्पिक K नोड्स को कैसे उल्टा करें और C++ कोड में स्यूडो-कोड कार्यान्वयन। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। इस दृष्टिकोण में, हमने वैकल्पिक K नोड्स को उल्टा करने और शेष नोड्स को छोड़ने के लिए पुनरावृत्ति का उपयोग किया। हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगा।

  1. C++ में लिंक्ड सूची के वैकल्पिक नोड्स का योग C++ में लिंक्ड सूची के वैकल्पिक नोड्स का योग

    इस समस्या में, हमें एक लिंक्ड सूची दी गई है। हमारा कार्य लिंक्ड सूची के वैकल्पिक नोड्स का योग प्रिंट करना है। लिंक्ड सूची डेटा संरचनाओं का एक क्रम है जो लिंक्स के माध्यम से एक साथ जुड़े हुए हैं। अब, आइए समस्या पर वापस आते हैं। यहां, हम लिंक्ड सूची के वैकल्पिक नोड्स को जोड़ेंगे। इसका मतलब है हम

  1. C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें

    हमें नोड्स के साथ एक सर्कुलर लिंक्ड लिस्ट दी गई है और कार्य सर्कुलर लिंक्ड लिस्ट में मौजूद नोड्स की संख्या की गणना करना है। सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट का एक प्रकार है जिसमें पहला तत्व अंतिम तत्व की ओर इंगित करता है और अंतिम तत्व पहले तत्व की ओर इंगित करता है। सिंगली लिंक्ड लिस्ट और डबली लिं

  1. C++ में पुनरावृत्ति का उपयोग करके लिंक्ड लिस्ट के वैकल्पिक नोड्स प्रिंट करें C++ में पुनरावृत्ति का उपयोग करके लिंक्ड लिस्ट के वैकल्पिक नोड्स प्रिंट करें

    लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जो तत्वों को गैर-सन्निहित मेमोरी स्थानों में संग्रहीत करती है। प्रत्येक तत्व में लिंक्ड लिस्ट के अगले तत्व का एक पॉइंटर होता है। उदाहरण - इस समस्या में, हमें एक लिंक्ड लिस्ट दी गई है और हमें इस लिंक्ड लिस्ट के तत्वों को प्रिंट करना है लेकिन केवल वैकल्पिक तत्वों