@@ -0,0 +1,1879 @@
+/*%0A * Key point: fast/slow runner technique to find the middle node%0A *       split to two lists from middle node%0A *       reverse the second list%0A *       merge the first list with the %0A *         reversed list, beginning with the original head%0A */%0A%0A/**%0A * Definition for singly-linked list.%0A * class ListNode %7B%0A *     int val;%0A *     ListNode next;%0A *     ListNode(int x) %7B%0A *         val = x;%0A *         next = null;%0A *     %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    public void reorderList(ListNode head) %7B%0A        if(head == null %7C%7C head.next == null %7C%7C head.next.next == null)%0A            return;%0A         %0A        //find the middle node    %0A        ListNode fast = head;%0A        ListNode slow = head;%0A        while(fast != null && fast.next != null)%7B%0A            slow = slow.next;%0A            fast = fast.next.next;%0A        %7D%0A        %0A        //reverse the second list%0A        ListNode newHead = slow.next;%0A        slow.next = null;%0A        newHead = reverseList(newHead);%0A        %0A        //merge the two lists%0A        ListNode current = head;%0A        ListNode newCurrent = newHead;        %0A        while(current != null && newCurrent != null)%7B%0A            ListNode next = current.next;%0A            ListNode newNext = newCurrent.next;%0A            %0A            current.next = newCurrent;%0A            newCurrent.next = next;%0A            %0A            current = next;%0A            newCurrent = newNext;%0A        %7D%0A%0A    %7D%0A    %0A    //function for reversing list%0A    public ListNode reverseList(ListNode head)%7B%0A        if(head == null %7C%7C head.next == null)%0A            return head;%0A        %0A        ListNode newHead = null;%0A        ListNode current = head;%0A        %0A        while(current != null)%7B%0A            ListNode next = current.next;%0A            current.next = newHead;%0A            newHead = current;%0A            current = next;%0A        %7D%0A        %0A        return newHead;%0A    %7D%0A%7D

Reorder List