2014
11-19

# LeetCode-Reorder List[链表]

### Reorder List

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}.

// LeetCode, Reorder List
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:

while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr; // cut at middle

slow = reverse(slow);

// merge two lists
while (curr->next) {
ListNode *tmp = curr->next;
curr->next = slow;
slow = slow->next;
curr->next->next = tmp;
curr = tmp;
}
curr->next = slow;
}

for (ListNode *curr = head->next, *next = curr->next; curr;
prev = curr, curr = next, next = next ? next->next : nullptr) {
curr->next = prev;
}
return prev;
}
};


Java代码:

/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {

while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}

ListNode mid = slow.next;
ListNode last = mid;
ListNode pre = null;
while(last != null){
ListNode next = last.next;
last.next = pre;
pre = last;
last = next;
}
slow.next = null;

while(head != null && pre != null){
}