C++에서 목록 재정렬

l1 -> l2 -> l3 -> l4 -> ... -> l(n-1) -> ln과 같은 연결 목록이 있다고 가정합니다. 이 목록을 l1 -> ln -> l2 -> l(n - 1) -> ... 등의 형식으로 재정렬해야 합니다. 여기서 제약 조건은 목록 노드의 값을 수정할 수 없으며 노드 자체만 변경할 수 있다는 것입니다. 예를 들어 목록이 [1,2,3,4,5]와 같으면 출력은 [1,5,2,4,3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 역방향 작업을 수행하려면 reverse라는 메소드를 정의하십시오. 이것은 노드 헤드와 노드 이전을 취합니다. 이것은 아래와 같이 작동합니다 -

• head가 null이면 prev

  를 반환합니다.

• temp :=머리 옆

• 다음 head :=prev, prev :=head

• 반환 역(temp, prev)

• 재정렬 작업은 아래와 같습니다 -

• 헤드가 null이면 null을 반환합니다.

• Slow 및 Fast라는 두 개의 노드 포인터를 정의하고 head로 초기화합니다.

• fast와 fast의 다음은 모두 null이 아니지만

  • 느린 :=느린 다음

  • fast :=빠른 다음의 다음

• 빠름 :=역방향(느림의 다음)

• 느린 다음을 null로 설정하고 slow :=head

• 두 개의 목록 노드 포인터 temp1 및 temp2 정의

• fast는 null이 아니지만

  • temp1 :=느린 다음, temp2 :=빠른 다음

  • 느린 다음 :=빠름, 빠른 다음 :=temp1

  • 느림 :=temp1, 빠름 :=temp2

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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);
}

입력

[1,2,3,4,5]

출력

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