企业官网建设流程全解析

143.重排链表

题目描述

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

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

Lo- 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

题目详解

# 找中间点 leetcode876defmiddleNode(self,head:ListNode|None)->ListNode|Node:slow=head fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslow

# 反转链表leetcode206defreverseList(self,head:ListNode|None)->ListNode|None:pre=Nonecur=headwhilecur:nxt=cur.nextcur.next=pre pre=cur cur=nxtreturnpre

第一次循环

defreorderList(self,head:Optional[ListNode])->None:mid=self.middleNode(head)#先找到中间节点head2=self.reverseList(mid)# 中间节点后面反转whilehead2.next:nxt1=head.next（节点2） nxt2=head2.next（节点4） head.next=head2 （节点5） head2.next=nxt1 （节点2） head=nxt1 （更新head） head2=nxt2(更新head2）

第2次循环

nxt1=head.next（节点3） nxt2=head2.next（节点3） head.next=head2(节点4） head2.next=nxt1 （节点3） head=nxt1 节点3head2=nxt2 节点3这次next2.next=空，不进入循环

head2 这条链，最后一个节点是中点，是 “终点哨兵”，不能拿来插。只要 head2 不是哨兵，就继续穿插。所以是while next2.next：

完整代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:# 反转链表206defreverseList(self,head:ListNode|None)->ListNode|None:pre=Nonecur=headwhilecur:nxt=cur.nextcur.next=pre pre=cur cur=nxtreturnpre# 找中间点 876defmiddleNode(self,head:ListNode|None)->ListNode|Node:slow=head fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslowdefreorderList(self,head:Optional[ListNode])->None:mid=self.middleNode(head)head2=self.reverseList(mid)whilehead2.next:nxt1=head.nextnxt2=head2.nexthead.next=head2 head2.next=nxt1 head=nxt1 head2=nxt2""" Do not return anything, modify head in-place instead. """

时间复杂度是O(N),空间复杂度是O（1）
求链表中间节点和反转链表的题目在前几篇文章有详细讲解，不理解的可以去前面翻看
后续会陆续出leetcode的题目解题过程，喜欢的小宝可以点赞收藏关注喔