题目

image.png

思路

  • 思路一：使用栈
  • 思路二：递归

  • 思路三：快慢指针+反转链表

    代码

    1.   //1.使用栈
    2.   public void reorderList(ListNode head) {
    3.       if (head == null || head.next == null || head.next.next == null) return;
    4.       LinkedList<ListNode> queue = new LinkedList<>();
    5.       while (head != null) {
    6.           queue.add(head);
    7.           head = head.next;
    8.       }
    9.       ListNode dummy = new ListNode(0);
    10.       while(!queue.isEmpty()) {
    11.           dummy.next = queue.pollFirst();
    12.           if (queue.isEmpty()) {
    13.               dummy.next.next = null;
    14.               return;
    15.           }
    16.           dummy.next.next = queue.pollLast();
    17.           dummy = dummy.next.next;
    18.           dummy.next = null;
    19.       }
    20.   }
    21.   //2.递归
    22.   ListNode dummy;
    23.   public void reorderList(ListNode head) {
    24.       if (head == null) return;
    25.       dummy = head;
    26.       recur(head.next);
    27.   }
    29.   public ListNode recur(ListNode tail) {
    30.       if (tail == null || tail.next == null) return tail;
    31.       ListNode nTail = recur(tail.next);
    32.       if (nTail == null) return nTail;
    33.       ListNode next = dummy.next;
    34.       dummy.next = nTail;
    35.       nTail.next = next;
    36.       dummy = next;
    37.       if ( tail == dummy || dummy.next == tail) {
    38.           tail.next = null;
    39.           return null;
    40.       }
    41.       return tail;
    42.   }

    重排链表