题目

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

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

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

题解

# Definition for singly-linked list.
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reorderList(self, head: ListNode) -> None:"""Do not return anything, modify head in-place instead."""# 寻找需插入的节点(找中点)if head is None or head.next is None:returnfast, last = head.next, headwhile fast and fast.next:fast = fast.next.nextlast = last.next# fast = None（长度奇数，待插入节点往后移一个） or last Node（长度偶数），eg:# 1 2 3 4 5# 1 5 2 4 3need_insert, last.next = last.next, None    # 记录待插入的节点，重置后最尾链表置为空# 反转待插入链表(头插法)tmp = ListNode()while need_insert:tmp.next, tmp.next.next, need_insert = need_insert, tmp.next, need_insert.nexttmp = tmp.next  # 将tmp指向反转后的首个节点# 依次插入while tmp:head.next, head.next.next, tmp = tmp, head.next, tmp.nexthead = head.next.nextdef print_list(head: ListNode):while head:print(head.val, end=' ')head = head.nextprint()if __name__ == '__main__':    a = ListNode(1, next=ListNode(2, next=ListNode(3, next=ListNode(4, next=ListNode(5)))))Solution().reorderList(a)print_list(a)