首页 > 代码库 > [LeetCode] Reorder List 链表重排序
[LeetCode] Reorder List 链表重排序
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes‘ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
这道链表重排序问题可以拆分为以下三个小问题：
1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。
2. 将第二个链翻转。
3. 将第二个链表的元素间隔地插入第一个链表中。
代码如下：
/** * 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 || !head->next->next) return; ListNode *fast = head; ListNode *slow = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } ListNode *mid = slow->next; slow->next = NULL; ListNode *last = mid; ListNode *pre = NULL; while (last) { ListNode *next = last->next; last->next = pre; pre = last; last = next; } while (head && pre) { ListNode *next = head->next; head->next = pre; pre = pre->next; head->next->next = next; head = next; } }};
[LeetCode] Reorder List 链表重排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。