Google+ Followers

Saturday, November 23, 2013

[LeetCode] Reorder List, Solution

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}.

[Thoughts]

目前想到的解法是,分三步来做:

1. 找出中间节点

2. 把中间节点之后的后半部分链表反序

3. 把前半部分链表及后半部分链表合并

 

[Code]

三步走解法

1 void reorderList(ListNode *head) {
2 if(head == NULL) return;
3 // find the median node
4 ListNode* fast = head;
5 ListNode* slow = head;
6 while(true)
7 {
8 fast = fast->next;
9 if(fast == NULL)
10 break;
11 fast = fast->next;
12 if(fast == NULL)
13 break;
14 slow = slow->next;
15 }
16
17 if(slow == NULL) return;
18
19 // reverse second half of link list
20 ListNode* cur = slow;
21 ListNode* pre = slow->next;
22 cur->next = NULL;
23 while(pre!=NULL)
24 {
25 ListNode* temp = pre->next;
26 pre->next = cur;
27 cur = pre;
28 pre = temp;
29 }
30
31 // merge two lists
32 ListNode* first = head;
33 ListNode* second = cur;
34
35 while(second!= NULL&& first!=NULL && first!=second)
36 {
37 ListNode* temp = second->next;
38 second->next = first->next;
39 first->next = second;
40 first = second->next;
41 second = temp;
42 }
43 }

应该有更漂亮的解法,还在思考中。

Post a Comment