/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if (!head || !head->next) return; ListNode* slow = head, *qulick = head->next; while (qulick && qulick->next) { slow = slow->next; qulick = qulick->next->next; } ListNode* left = head, *right = slow->next; slow->next = nullptr; right = reverse(right); ListNode* p = left, *q = right, *dummy = new ListNode(-1), *tail = dummy; while (p && q) { tail->next = p; tail = p; p = p->next; tail->next = q; tail = q; q = q->next; } if (p) tail->next = p; } ListNode* reverse(ListNode* head) { if (!head || !head->next) return head; ListNode* newHead = reverse(head->next); head->next->next = head; head->next = nullptr; return newHead; } };