143.Reorder List (M)

https://leetcode.com/problems/reorder-list/

1.Description(Medium)

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].

• 1 <= Node.val <= 1000

2.Code

1.找中点（Middle）

2.反转（Reverse）

3.Merge(加一个index来判断奇偶)

public void reorderList(ListNode head) { 
        if(head==null ||head.next==null){
            return;
        }

        ListNode mid=middleNode(head);
        ListNode right=reverse(mid.next);
        mid.next=null;  //caution

        merge(head,right);        

    }


    public ListNode reverse(ListNode head) {

            ListNode prev = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = prev;
                prev = head;
                head = temp;
            }
            return prev;
        }

    public void merge(ListNode head1,ListNode head2){

        int index=0;
        ListNode dummy=new ListNode(0);
        while(head1!=null && head2!=null){
            if(index%2==0){
                dummy.next=head1;
                head1=head1.next;
            }
            else{
                dummy.next=head2;
                head2=head2.next;
            }
            dummy=dummy.next;
            index++;
        }

        if(head1!=null){
            dummy.next=head1;
        }
        if(head2!=null){
            dummy.next=head2;
        }

    }

     public ListNode middleNode(ListNode head) { 

            ListNode slow=head;
            ListNode fast=head.next;

            while(fast!=null && fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }

            return slow;
        }