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}.
Leetcode link
Lintcode link
Solution:
First, we can find the middle point of the list.
Then reverse the list behind the middle point.
Finally merge them together.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
> File Name: ReorderList.java
> Author: Yao Zhang
> Mail: psyyz10@163.com
> Created Time: Fri 20 Nov 13:21:59 2015
************************************************************************/
public class ReorderList{
public void reorderList(ListNode head) {
if (head == null)
return;
ListNode mid = findMiddle(head);
ListNode tail = reverse(mid.next);
mid.next = null;
merge(head, tail);
}
public void merge(ListNode node1, ListNode node2){
ListNode dummy = new ListNode(-1);
while (node1 != null && node2 != null){
dummy.next = node1;
node1 = node1.next;
dummy.next.next = node2;
node2 = node2.next;
dummy = dummy.next.next;
}
if (node1 != null)
dummy.next = node1;
else if (node2 != null)
dummy.next = node2;
}
public ListNode reverse(ListNode head){
ListNode prev = null;
while (head != null){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
public ListNode findMiddle(ListNode head){
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
|