143. 重排链表

难度: 中等

来源: 每日一题 2023.07.31

---

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {

    }
}

分析与题解

---

• 双向队列法

  利用一个双向队列,然后把所有的节点入队; 然后每次从头部和尾部各取一个节点, 添加到重构的链表中. 这样即可完成整个题目的题解.

  • 首先, 创建一个双向队列, 然后把所有的节点进行入队.

    Deque <ListNode> deque = new ArrayDeque<ListNode>();
    ListNode node = head;
    while (node != null) {
        deque.add(node);
        node = node.next;
    }
    

  • 然后就是每一次循环都把队首和队尾节点弹出, 知道队列为空则停止.

    node = null;
    while(!deque.isEmpty()) {
        ListNode header = deque.pollFirst();
        if (header != null) {
            if (node == null) {
                node = header;
                head = node;
            } else {
                node.next = header;
                node = header;
            }
        }
        ListNode total = deque.pollLast();
        if (total != null) {
            node.next = total;
            node = total;
        }
    }
    

  • 同时需要把链表最后一个节点的 next成员变量 置为 null

    node.next = null;
    

  整个解题过程如下所示.

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode() {}
  *     ListNode(int val) { this.val = val; }
  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  * }
  */
  class Solution {
      public void reorderList(ListNode head) {
          // 双向队列实现
          Deque <ListNode> deque = new ArrayDeque<ListNode>();
          ListNode node = head;
          while (node != null) {
              deque.add(node);
              node = node.next;
          }
          node = null;
          while(!deque.isEmpty()) {
              ListNode header = deque.pollFirst();
              if (header != null) {
                  if (node == null) {
                      node = header;
                      head = node;
                  } else {
                      node.next = header;
                      node = header;
                  }
              }
              ListNode total = deque.pollLast();
              if (total != null) {
                  node.next = total;
                  node = total;
              }
          }
          node.next = null;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(2n)
  • 空间复杂度: O(n)

  结果如下所示.