重排链表(Leetcode)

题目地址重排链表

思考

此题如果要求时间复杂度和空间复杂度都为O(n)的前提下很简单，我们遍历链表存入数据，而后读取数据重建链表即可。

但此题出现在2019年408考研真题的第41题。

那么就很有必要思考O(1)的空间复杂度的解法。

链表只能正向遍历，那么我们可以将原链表从中间分开，前者不动，而后对后面的链表进行倒序反转，而后得到的两条链表，在第一条链表的基础上进行重建。

完整代码

class Solution { public: ListNode* reverse_list(ListNode* head) {//反转链表,我们让该节点的指针指向上一个节点，循环，即可 ListNode* pre = nullptr; ListNode* temp;//保存下一个节点 ListNode* cur = head; while (cur) { temp = cur->next;//下一个要反转的节点 cur->next = pre;//next指向上一个节点 pre = cur; cur = temp; } return pre; } void reorderList(ListNode* head) { if (head == nullptr) return; ListNode* slow = head, * fast = head; //快慢指针寻找链表中点 while (fast && fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } ListNode* head1 = head; ListNode* head2 = slow->next; slow->next = nullptr;//隔开链表 head2 = reverse_list(head2); ListNode* cur1 = head1; ListNode* cur2 = head2; ListNode* cur = head;//在head基础上重建 cur1 = cur1->next; int count = 0; 偶数取head2的元素，奇数取head1的元素 while (cur1 && cur2) { if (count % 2 == 0) { cur->next = cur2; cur2 = cur2->next; } else { cur->next = cur1; cur1 = cur1->next; } count++; cur = cur->next; } if (cur2 != nullptr) // 处理结尾 cur->next = cur2; if (cur1 != nullptr) cur->next = cur1; } };