编程开发Reorder List求解

编程开发Reorder List求解

Given a singly linked listL: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}.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null){
            return;
        }
        head = reverLastHalfNodes(head);
        ListNode fast = head, slow = head, first = head;
        while (fast != null&&fast.next != null&&fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        while (first != null){
            ListNode n0 = first.next;
            ListNode n1 = null;
            if (tmp != null){
                n1 = tmp.next;
                first.next = tmp;
                tmp.next = n0; 
            }
            tmp = n1;    
            first = n0;
        }
    }
    
    public ListNode reverLastHalfNodes(ListNode head){
        ListNode fast = head, slow = head;
        while (fast != null&&fast.next != null&&fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow;
        ListNode t = null;
        slow = slow.next;
        while (slow != null){
            ListNode n = slow.next;
            slow.next = t;
            t = slow;
            slow = n;
        }
        tmp.next = t;
        return head;
    }
}