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. 把前半部分链表及后半部分链表合并
Solution 1:
自己的代码，写得太乱了。。。很多地方可以改进的。。。
1 /**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9 * }
10 * }
11 */
12 public class Solution {
13 public void reorderList(ListNode head) {
14 if(head==null||head.next==null)
15 return;
16 ListNode fast=head;
17 ListNode slow=head;
18 while(fast.next!=null&&fast.next.next!=null){
19 fast=fast.next.next;
20 slow=slow.next;
21 }
22 ListNode head2=slow.next;
23 slow.next=null;
24 head2=reverseList(head2);
25 while(head!=null&&head2!=null){
26 ListNode temp=head.next;
27 head.next=head2;
28 ListNode temp2=head2.next;
29 head2.next=temp;
30 head=temp;
31 head2=temp2;
32 }
33 }
34
35 private ListNode reverseList(ListNode head) {
36
37 if(head==null||head.next==null)
38 return head;
39 // TODO Auto-generated method stub
40 ListNode dummy=new ListNode(-1);
41 dummy.next=head;
42 ListNode pre,l1,l2,l3;
43 pre=dummy;
44 l1=pre.next;
45 ListNode last=l1;
46 l2=l1.next;
47 l3=l2.next;
48 while(l3!=null){
49 l2.next=l1;
50 l1=l2;
51 l2=l3;
52 l3=l3.next;
53 }
54 dummy.next=l2;
55 l2.next=l1;
56 last.next=null;
57 return dummy.next;
58 }
59 }
Solution 2:
大神的代码：
1 public class ReorderList {
2 public void reorderList(ListNode head) {
3 if (head == null || head.next == null)
4 return;
5 ListNode fast = head;
6 ListNode late = head;
7 while (fast.next != null && fast.next.next != null) {
8 fast = fast.next.next;
9 late = late.next;
10 }
11 ListNode ret = new ListNode(0);
12 ListNode cur = ret;
13 ListNode leftHalf = head;
14 ListNode rightHalf;
15 if (fast.next != null) {
16 rightHalf = reverseList(late.next);
17 late.next = null;
18 } else {
19 rightHalf = reverseList(late);
20 ListNode tmp = head;
21 while (tmp.next != late) {
22 tmp = tmp.next;
23 }
24 tmp.next = null;
25 }
26 leftHalf = head;
27 while (leftHalf != null && rightHalf != null) {
28 cur.next = leftHalf;
29 leftHalf = leftHalf.next;
30 cur = cur.next;
31 cur.next = rightHalf;
32 rightHalf = rightHalf.next;
33 cur = cur.next;
34 }
35 if (leftHalf != null) {
36 cur.next = leftHalf;
37 } else if (rightHalf != null) {
38 cur.next = rightHalf;
39 }
40 head = ret.next;
41 }
42
43 private ListNode reverseList(ListNode head) {
44 ListNode cur = head;
45 ListNode prev = null;
46 ListNode next = null;
47 while (cur != null) {
48 next = cur.next;
49 cur.next = prev;
50 prev = cur;
51 cur = next;
52 }
53 return prev;
54 }
55 }