@@ -0,0 +1,1876 @@
+/**%0A * Name: Reorder List%0A * Number: 143%0A * Main Points:%0A   3 steps: %0A   Find the middle of the list%0A   Reverse the half after middle  1-%3E2-%3E3-%3E4-%3E5-%3E6-%3Enull to 1-%3E2-%3E3-%3Enull 6-%3E5-%3E4-%3Enull%0A   merge to 1-%3E6-%3E2-%3E5-%3E3-%3E4%0A * Time Complexity: O(n)%0A * Space Complexity: O(1)%0A**/%0A/**%0A * Definition for singly-linked list.%0A * public class ListNode %7B%0A *     int val;%0A *     ListNode next;%0A *     ListNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Aclass Solution %7B%0A    public void reorderList(ListNode head) %7B%0A        if (head == null %7C%7C head.next == null) return;%0A        //find middle%0A        ListNode mid = findMiddle(head);%0A        //reverse linkedlist%0A        ListNode tail = reverse(mid.next);%0A        mid.next = null;%0A        //merge tow linkedlist%0A        merge(head, tail);%0A    %7D%0A    private ListNode findMiddle(ListNode head) %7B%0A        ListNode slow = head, fast = head.next;%0A        while (fast != null && fast.next != null) %7B%0A            slow = slow.next;%0A            fast = fast.next.next;%0A        %7D%0A        return slow;%0A    %7D%0A    %0A    private ListNode reverse(ListNode head) %7B%0A        ListNode newHead = null;%0A        while (head != null) %7B%0A            ListNode next = head.next;%0A            head.next = newHead;%0A            newHead = head;%0A            head = next;%0A        %7D%0A        return newHead;%0A    %7D%0A    %0A    private void merge(ListNode head1, ListNode head2) %7B%0A        int index = 0;%0A        ListNode dummy = new ListNode(0);%0A        while (head1 != null && head2 != null) %7B%0A            if (index %25 2 == 0) %7B%0A                dummy.next = head1;%0A                head1 = head1.next;%0A            %7D else %7B%0A                dummy.next = head2;%0A                head2 = head2.next;%0A            %7D%0A            dummy = dummy.next;%0A            index++;%0A        %7D%0A        if (head1 != null) %7B%0A            dummy.next = head1;%0A        %7D else %7B%0A            dummy.next = head2;%0A        %7D%0A    %7D%0A%7D

find middle, reverse, merge