Sắp xếp lại danh sách liên kết trong C++

Cho danh sách liên kết L1→L2→L3→L4→…→L(n-1)→Ln. Sắp xếp lại thành L1→Ln→L2→L(n-1)→…. Không được sửa giá trị nút, chỉ đổi liên kết. Ví dụ: [1,2,3,4,5] → [1,5,2,4,3].

Giải thuật

• Hàm reverse(head, prev) đảo ngược danh sách:
  • Nếu head == null trả về prev.
  • temp = head->next, head->next = prev, prev = head.
  • Trả về reverse(temp, prev).
• Hàm reorderList(head):
  • Nếu head == null trả về.
  • slow = head, fast = head.
  • Khi fast && fast->next: slow = slow->next; fast = fast->next->next.
  • fast = reverse(slow->next), slow->next = NULL, slow = head.
  • Khi fast != null:
    • temp1 = slow->next, temp2 = fast->next.
    • slow->next = fast, fast->next = temp1.
    • slow = temp1, fast = temp2.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) { val = data; next = NULL; }
};

class Solution {
public:
    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, *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;
        }
    }
};

Đầu vào

[1,2,3,4,5]

Đầu ra

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