143. Reorder List

题目143. Reorder List

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}

思路:使用快慢指针找到链表的中点,然后将后半部分插入前半部分

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return ;
        }
        
        ListNode lowerNode = head;
        ListNode fastNode = head;
        while(fastNode.next != null && fastNode.next.next != null){
            lowerNode = lowerNode.next;
            fastNode = fastNode.next.next;
        }
        
        ListNode secondNode = lowerNode.next;
        lowerNode.next = null;
        ListNode secondHead = new ListNode(1);
        ListNode tempNode = null;
        while(secondNode != null){
            tempNode = secondNode.next;
            secondNode.next = secondHead.next;
            secondHead.next = secondNode;
            secondNode = tempNode;
        }
        
        secondNode = secondHead.next;
        ListNode firstNode = head;
        
        ListNode tempFirst = null;
        ListNode tempSecond = null;
        while(secondNode != null){
            tempFirst = firstNode.next;
            tempSecond = secondNode.next;
            secondNode.next = firstNode.next;
            firstNode.next = secondNode;
            firstNode = tempFirst;
            secondNode = tempSecond;
        }
       
    }
}