题解 | #重排链表#

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null)
        {
            return;
        }
        int count = 0;
        ListNode cur = head;
        Deque<ListNode> stack  = new LinkedList<>();
        Deque<ListNode> queue = new LinkedList<>();
        while(cur != null)
        {   
           queue.add(cur);
           stack.push(cur);

            cur = cur.next;
            count++;
        }
        ListNode tmp = head;
        int flag = 0;
        int COUNT = 1;
        while(true)
        {
            if(flag == 0)
            {
                queue.poll().next = stack.peek();
                COUNT++;
                flag = 1;
            }
            else{
                stack.pop().next = queue.peek();
                flag = 0;
                COUNT++;
            }
            if(COUNT == count)
            {   
                if(COUNT % 2 ==1)
                {
                    stack.peek().next = null;
                }
                else{
                    queue.peek().next = null;
                }
                break;
            }
        }
    }
}