还不快抢沙发

添加新评论

给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: ``` 给定链表 1->2->3->4, 重新排列为 1->4->2->3. ``` 示例 2: ``` 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. ``` 解答: ``` ListNode* reorderList(ListNode* head) { if (!head) return head; ListNode* h = head; vector collection; while (h) { collection.push_back(h); h = h->next; } int size = collection.size(); int n = size / 2; for (int i = 0; i < n; i++) { int right = size - 1 - i; collection[i]->next = collection[right]; collection[right]->next = collection[i + 1]; if (i == n - 1 && size % 2 == 0) { collection[right]->next = nullptr; } if (i == n - 1 && size % 2 != 0) { collection[right]->next->next = nullptr; } } return head; } ```