143.重排链表

链接：143.重排链表
难度：Medium
标签：栈、递归、链表、双指针
简介：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…。

题解 1 - typescript

• 编辑时间：2020-10-20
• 执行用时：208ms
• 内存消耗：47MB
• 编程语言：typescript
• 解法介绍：利用队列前后取值进行重新赋值 next。

function reorderList(head: ListNode | null): void {
  if (head === null) return;
  const queue: ListNode[] = [];
  let temp: ListNode | null = head;
  while (temp !== null) {
    queue.push(temp);
    temp = temp.next;
  }
  queue.shift();
  let tag = true;
  temp = head;
  while (queue.length !== 0) {
    temp.next = (tag = !tag) ? queue.shift()! : queue.pop()!;
    temp = temp!.next;
  }
  temp.next = null;
}

题解 2 - cpp

• 编辑时间：2023-07-31
• 执行用时：40ms
• 内存消耗：17.2MB
• 编程语言：cpp
• 解法介绍：找到中点，翻转后半部分，合并。

class Solution {
public:
    void reorderList(ListNode* head) {
        // mid
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // reverse
        ListNode *last = slow->next;
        if (!last) return;
        while (last->next) {
            ListNode *tmp = last->next;
            last->next = tmp->next;
            tmp->next = slow->next;
            slow->next = tmp;
        }
        // merge
        ListNode *l1 = head, *l2 = slow->next;
        while (l1 && l2) {
            ListNode *tmp1 = l1->next, *tmp2 = l2->next;
            l1->next = l2;
            l2->next = tmp1;
            l1 = tmp1;
            l2 = tmp2;
        }
        // last node
        slow->next = nullptr;
    }
};

题解 3 - python

• 编辑时间：2023-07-31
• 执行用时：76ms
• 内存消耗：24.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        last = slow.next
        if not last:
            return
        while last.next:
            tmp = last.next
            last.next = tmp.next
            tmp.next = slow.next
            slow.next = tmp
        l1 = head
        l2 = slow.next
        while l1 and l2:
            tmp1 = l1.next
            tmp2 = l2.next
            l1.next = l2
            l2.next = tmp1
            l1 = tmp1
            l2 = tmp2
        slow.next = None