Sắp xếp lại danh sách trong C ++

Giả sử chúng ta có một danh sách liên kết như l1 -> l2 -> l3 -> l4 ->… -> l (n-1) -> ln. Chúng ta phải sắp xếp lại danh sách này thành dạng l1 -> ln -> l2 -> l (n - 1) ->…, v.v. Ở đây, hạn chế là, chúng ta không thể sửa đổi các giá trị trong các nút danh sách, chỉ có thể thay đổi chính nút đó. Vì vậy, ví dụ:nếu danh sách giống như [1,2,3,4,5], thì đầu ra sẽ là [1,5,2,4,3]

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

• Xác định một phương thức được gọi là đảo ngược để thực hiện thao tác ngược lại. Điều này sẽ chiếm đầu nút và nút chiếm ưu thế. Điều này sẽ hoạt động như dưới đây -

• nếu head là null, thì trả về trước

• temp:=next of head

• tiếp theo của đầu:=trước, và trước:=đầu

• trả về đảo ngược (tạm thời, trước)

• Nhiệm vụ sắp xếp lại sẽ giống như bên dưới -

• nếu head là null, thì trả về null

• xác định hai con trỏ nút được gọi là chậm và nhanh và khởi tạo chúng bằng head

• trong khi nhanh và tiếp theo của nhanh cả hai đều không rỗng,

  • chậm:=tiếp theo của chậm

  • fast:=next of next of fast

• nhanh:=đảo ngược (tiếp theo của chậm)

• đặt tiếp theo của slow as null và slow:=head

• xác định hai con trỏ nút danh sách temp1 và temp2

• trong khi nhanh không phải là rỗng

  • temp1:=tiếp theo của chậm, temp2:=tiếp theo của nhanh

  • tiếp theo của chậm:=nhanh, tiếp theo của nhanh:=temp1

  • chậm:=temp1, nhanh:=temp2

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){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* successor = NULL;
   ListNode* reverse(ListNode* head, ListNode* prev = NULL){
      if(!head)return prev;
      ListNode* temp = head->next;
      head->next = prev;
      prev = head;
      return reverse(temp, prev);
   }
   void reorderList(ListNode* head) {
      if(!head)return;
      ListNode* slow = head;
      ListNode* fast = head;
      while(fast && fast->next){
         slow = slow->next;
         fast = fast->next->next;
      }
      fast = reverse(slow->next);
      slow->next = NULL;
      slow = head;
      ListNode *temp1, *temp2;
      while(fast){
         temp1 = slow->next;
         temp2 = fast->next;
         slow->next = fast;
         fast->next = temp1;
         slow = temp1;
         fast = temp2;
      }
   }
};
main(){
   vector<int> v = {1,2,3,4,5};
   ListNode *h1 = make_list(v);
   Solution ob;
   (ob.reorderList(h1));
   print_list(h1);
}

Đầu vào

[1,2,3,4,5]

Đầu ra

[1, 5, 2, 4, 3, ]