问题

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

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路

首先观察重排以后的链表，会发现是头尾交替连接的
那么我们可以当作是两个链表的交叉合并
image.png
给定链表 1->2->3->4, 重新排列为 1->4->2->3
要合并的这两个链表其中一个是链表的前半部分，另一个是链表后半部分的反转

这样我们就把问题转化成几个子问题：找到链表的中间节点，对后半部分的链表进行反转、合并两个链表

时间复杂度：O(n)
空间复杂度：O(1)

程序

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reorderList(self, head: ListNode) -> None:
  8.         """
  9.         Do not return anything, modify head in-place instead.
  10.         """
  11.         dummy = ListNode(0)
  12.         dummy.next = head
  13.         # 找到中间节点
  14.         low = dummy
  15.         fast = dummy
  16.         while fast and fast.next:
  17.             low = low.next
  18.             fast = fast.next.next
  19.         mid = low.next
  20.         low.next = None
  21.         # 反转
  22.         mid = self.reverse(mid)
  23.         # 交叉合并两个链表
  24.         self.merge_two_list(dummy.next, mid)
  26.     # 反转链表
  27.     def reverse(self, head: ListNode) -> ListNode:
  28.         if not head:
  29.             return None
  30.         cur = None
  31.         while head:
  32.             node = head.next
  33.             head.next = cur
  34.             cur = head
  35.             head = node
  36.         return cur
  38.     # 交叉合并两个链表    
  39.     def merge_two_list(self, l1: ListNode, l2: ListNode) -> ListNode:
  40.         dummy = ListNode(0)
  41.         cur = dummy
  42.         while l1 and l2:
  43.             # 先连 l1
  44.             cur.next = l1
  45.             cur = cur.next
  46.             l1 = l1.next
  48.             # 再连 l2
  49.             cur.next = l2
  50.             cur = cur.next
  51.             l2 = l2.next
  52.         # 对剩下的部分进行单独处理
  53.         if l1:
  54.             cur.next = l1
  55.         if l2:
  56.             cur.next = l2
  58.         return dummy.next