Question:

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

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return;
        ListNode temp = head;
        int count = 1;  //record the amount of the total nodes
        while (temp.next != null) {
            temp = temp.next;
            count++;
        }
        // get the middle node of this linked list
        int middle = count / 2;
        ListNode middleNode = head;
        for (int i = 1; i < middle; i++)
            middleNode = middleNode.next;
        // reverse the right half linked list
        ListNode tail = middleNode;
        for (int i = middle; i < count; i++)
            tail = tail.next;
        reverseLinkedList(middleNode.next);
        middleNode.next = tail;
        // insert nodes
        temp = head;
        ListNode rightHead = middleNode.next;
        ListNode temp2 = null;
        int i = 1;
        while (i < middle) {
            temp2 = rightHead.next;
            rightHead.next = temp.next;
            temp.next = rightHead;  
            temp = rightHead.next;
            rightHead = temp2;
            middleNode.next = rightHead;
            i++;
        }
    }
    
    private ListNode reverseLinkedList(ListNode head) {
        if (head == null)
            return null;
        ListNode temp = reverseLinkedList(head.next);
        if (temp == null)
            return head;
        temp.next = head;
        head.next = null;
        return head;
    }
}

My test result:

Paste_Image.png

這次作業(yè)一開始我是用另外一種方法寫的，遞歸。但是我自己也知道，復(fù)雜度太大了。提交代碼后發(fā)現(xiàn)，果然超出限定時(shí)間了。于是只能去看網(wǎng)友的提示。然后寫出了現(xiàn)在的代碼。
他把這個(gè)reorder分為了三個(gè)步驟。
第一個(gè)步驟，找到 middle node.
第二個(gè)步驟，reverse 后半段 鏈表。
第三個(gè)步驟，一個(gè)個(gè)插入進(jìn)去。
為什么我沒能想到呢？我喜歡思考這個(gè)問題。
還是那個(gè)原因，同樣的問題，我們的出發(fā)點(diǎn)不同，導(dǎo)致最后寫出來的復(fù)雜度就完全不同了。
不過，趁這個(gè)機(jī)會(huì)，復(fù)習(xí)了下reverse the linked list，同時(shí)，第三個(gè)步驟插入，需要有個(gè)將后半段與前半段鏈表連接起來的小操作。
貼一下我自己寫的代碼：

public class Solution {
    
    public void reorderList(ListNode head) {
        if (head == null)
            return;
        reorder(head);
    }
    
    private void reorder(ListNode head) {
        if (head.next == null)
            return;
        ListNode subListHead = head.next;
        ListNode temp = subListHead;
        if (temp.next == null)
            return;
        while (temp.next.next != null)
            temp = temp.next;
        ListNode subListTail = temp.next;
        if (subListTail == subListHead.next) {
            head.next = subListTail;
            subListTail.next = subListHead;
            subListHead.next = null;
            return;
        }
        else {
            temp.next = null;
            head.next = subListTail;
            subListTail.next = subListHead;     
            reorder(subListHead);
        }
    }
   } 

**
總結(jié)：當(dāng)復(fù)雜度過高的時(shí)候，就不是寫代碼的問題了，是你思考問題的角度不對(duì)。這個(gè)時(shí)候就像換種想法去解決這個(gè)問題了，而不要固守在這個(gè)問題上。
反轉(zhuǎn)鏈表： 遞歸的話，就是。。。。好，我腦子里想了一遍，就不打出來了，不知道怎么表達(dá)。
**
本來想專心學(xué)習(xí)CS一段時(shí)間的，但發(fā)現(xiàn)還是有好多事情等著自己去做。
機(jī)票還沒買。
日本行。
家里那么多親戚，爸媽的朋友都等著請(qǐng)我吃飯。
高中同學(xué)。
哎，好多事。
我現(xiàn)在最想的，就是給我一年的時(shí)間，讓我安靜學(xué)習(xí)下計(jì)算機(jī)，我真的感興趣。
昨天出去散步，路上回家，碰到了小學(xué)的班主任。她還記得我。哈哈，我這么優(yōu)秀她怎么會(huì)忘了我。我覺得我應(yīng)該是我小學(xué)班上的異類吧。我的小學(xué)算是鄉(xiāng)下，班里的大多數(shù)現(xiàn)在都工作了，有些已經(jīng)結(jié)婚了，甚至有小孩了。
而我，還在作死。
把自己這幾年念的大學(xué)和老師講了。。。結(jié)果她一所都沒聽過。
我本來想衣錦還鄉(xiāng)的，現(xiàn)在。。。怎么還鄉(xiāng)。。。
Anyway, Good luck, Richardo!

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;
        slow.next = null;
        fast = reverse(head2);
        slow = head;
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (slow != null && fast != null) {
            curr.next = slow;
            slow = slow.next;
            curr = curr.next;
            curr.next = fast;
            fast = fast.next;
            curr = curr.next;
        }
        
        if (slow != null) {
            curr.next = slow;
        }
    }
    
    private ListNode reverse(ListNode head) {
        ListNode pre = head;
        ListNode curr = head.next;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        head.next = null;
        return pre;
    }
}

這道題目沒什么難點(diǎn)。就是找到中點(diǎn)，然后斷開其與下一個(gè)節(jié)點(diǎn)的聯(lián)系。然后reverse右半部分的鏈表，然后merge

Anyway, Good luck, Richardo! -- 08/16/2016