Chương trình hoán đổi các nút của một cặp danh sách liên kết khôn ngoan trong C ++

Giả sử chúng ta có một danh sách liên kết. Chúng ta phải hoán đổi mỗi hai nút liền kề (cặp) và trả về phần đầu của nó. Ở đây ràng buộc là, chúng ta không thể sửa đổi giá trị của các nút, chỉ có thể thay đổi chính nút đó. Vì vậy, nếu danh sách giống như [1,2,3,4], thì danh sách kết quả sẽ là [2,1,4,3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu phần đầu không xuất hiện, thì hãy quay lại phần đầu
• first:=head, second:=next of head, dummy là một nút mới có giá trị -1
• tiếp theo của dummy:=đầu tiên và trước:=dummy
• while thứ hai không rỗng
  • temp:=next of second
  • next of first:=next of second
  • tiếp theo của giây:=đầu tiên
  • tiếp theo của trước:=thứ hai
  • trước:=đầu tiên
  • nếu tạm thời không null, thì đầu tiên:=tạm thời và thứ hai:=tiếp theo của nhiệt độ, nếu không thì ngắt
• trở lại tiếp theo của hình nộm

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
void print_list(ListNode *head){
   ListNode *ptr = head;
   cout << "[";
   while(ptr->next){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
public:
   ListNode* swapPairs(ListNode* head) {
      if(!head)return head;
         ListNode* first= head;
         ListNode* second = head->next;
         ListNode* dummy = new ListNode(-1);
         dummy->next = first;
         ListNode* prev = dummy;
         while(second){
            ListNode* temp = second->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            if(temp){
               first = temp;
               second = temp ->next;
            }
            else break;
      }
      return dummy->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
   ListNode *head = make_list(v);
   print_list(ob.swapPairs(head));
}

Đầu vào

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Đầu ra

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13,]