fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Node structure for linked list
  5. struct Node {
  6.     int data;
  7.     Node* next;
  8.     Node(int val) : data(val), next(NULL) {}
  9. };
  10.  
  11. // Function to insert at end
  12. void insertEnd(Node*& head, int val) {
  13.     Node* newNode = new Node(val);
  14.     if (!head) {
  15.         head = newNode;
  16.         return;
  17.     }
  18.     Node* temp = head;
  19.     while (temp->next) temp = temp->next;
  20.     temp->next = newNode;
  21. }
  22.  
  23. // Function to print linked list
  24. void printList(Node* head) {
  25.     while (head) {
  26.         cout << head->data;
  27.         if (head->next) cout << "->";
  28.         head = head->next;
  29.     }
  30.     cout << "\n";
  31. }
  32.  
  33. // Reverse entire linked list
  34. Node* reverseList(Node* head) {
  35.     Node* prev = NULL;
  36.     Node* curr = head;
  37.     while (curr) {
  38.         Node* nextNode = curr->next;
  39.         curr->next = prev;
  40.         prev = curr;
  41.         curr = nextNode;
  42.     }
  43.     return prev;
  44. }
  45.  
  46. // Clone linked list (without random pointer)
  47. Node* cloneList(Node* head) {
  48.     if (!head) return NULL;
  49.     Node* newHead = new Node(head->data);
  50.     Node* tempNew = newHead;
  51.     Node* tempOld = head->next;
  52.     while (tempOld) {
  53.         tempNew->next = new Node(tempOld->data);
  54.         tempNew = tempNew->next;
  55.         tempOld = tempOld->next;
  56.     }
  57.     return newHead;
  58. }
  59.  
  60. // Reverse K nodes in-place
  61. Node* reverseKGroup(Node* head, int k) {
  62.     Node* curr = head;
  63.     int count = 0;
  64.  
  65.     // Check if we have k nodes
  66.     Node* temp = head;
  67.     for (int i = 0; i < k; i++) {
  68.         if (!temp) return head;
  69.         temp = temp->next;
  70.     }
  71.  
  72.     Node* prev = NULL;
  73.     Node* nextNode = NULL;
  74.  
  75.     // Reverse first k nodes
  76.     while (curr && count < k) {
  77.         nextNode = curr->next;
  78.         curr->next = prev;
  79.         prev = curr;
  80.         curr = nextNode;
  81.         count++;
  82.     }
  83.  
  84.     // Recursive call for the rest
  85.     if (nextNode) head->next = reverseKGroup(nextNode, k);
  86.  
  87.     return prev;
  88. }
  89.  
  90. int main() {
  91.     Node* head = NULL;
  92.  
  93.     // Create Linked List: 1->2->3->4->5
  94.     insertEnd(head, 1);
  95.     insertEnd(head, 2);
  96.     insertEnd(head, 3);
  97.     insertEnd(head, 4);
  98.     insertEnd(head, 5);
  99.  
  100.     cout << "Original List: ";
  101.     printList(head);
  102.  
  103.     // Reverse entire list
  104.     Node* rev = reverseList(head);
  105.     cout << "Reversed List: ";
  106.     printList(rev);
  107.  
  108.     // Clone list
  109.     Node* clone = cloneList(rev);
  110.     cout << "Cloned List: ";
  111.     printList(clone);
  112.  
  113.     // Reverse every K nodes
  114.     int k = 2;
  115.     Node* kRev = reverseKGroup(clone, k);
  116.     cout << "K-Group Reversed List (k=" << k << "): ";
  117.     printList(kRev);
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original List: 1->2->3->4->5
Reversed List: 5->4->3->2->1
Cloned List: 5->4->3->2->1
K-Group Reversed List (k=2): 4->5->2->3->1
https://ideone.com/chcjCB
language:
C++14 (gcc 8.3)
created:
21 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!