首页 > 代码库 > 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)in-place (2)not altering the nodes‘ values。最简单的方式是brute force，先找到last node，然后插入到相应的位置，重复上述过程直到遇到原来的中间节点变为last node或者second last node。brute force的时间复杂度是O(n^2)。但此题有O(n)的解法，先找到中间节点，然后将原来的list断成前后两部分，对后半部分list进行reverse操作，再与前半部分list merge。O(n)解法代码如下：
class Solution {public: void reorderList(ListNode *head) { if(head == NULL || head->next == NULL || head->next->next == NULL) return; int len = 0; for(ListNode *p = head; p; p = p->next) len++; ListNode *mid = head; for(int i = 0; i < len/2; i++) mid = mid->next; ListNode *sec_head = reverse(mid->next); mid->next = NULL; merge(head, sec_head); } ListNode * reverse(ListNode *head){ if(head == NULL || head->next == NULL) return head; ListNode *dummy = new ListNode(-1); dummy->next = head; for(ListNode *prev = head, *p = head->next; p; p = prev->next){ prev->next = p->next; p->next = dummy->next; dummy->next = p; } return dummy->next; } void merge(ListNode *head1, ListNode *head2){ while(head1 && head2){ ListNode *tmp1 = head1->next; ListNode *tmp2 = head2->next; head1->next = head2; head2->next = tmp1; head1 = tmp1; head2 = tmp2; } }};
Leetcode: Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。