LeetCode 143. 重排链表

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 143. 重排链表

思路分析

获取链表的中间节点 slow(如果链表的长度为偶数，有两个中间结点，则返回第一个中间结点。)

从中间节点的下一个节点开始反转后半部分链表, 反转后 pre 为新链表的头节点

合并两个链表

参考代码

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	var pre *ListNode
	cur := slow.Next
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	slow.Next = nil
	p1, p2 := head, pre
	for p2 != nil {
		next1, next2 := p1.Next, p2.Next
		p1.Next = p2
		p2.Next = next1
		p1 = next1
		p2 = next2
	}
}

找到链表中点：使用快慢指针找到链表的中点。

反转后半部分链表：将链表的后半部分反转。

合并两个链表：将前半部分和反转后的后半部分链表合并。

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}

	// 找到链表的中间节点
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 反转链表的后半部分
	var pre *ListNode
	cur := slow
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	// 合并两个链表
	first, second := head, pre
	for second != nil && second.Next != nil {
		firstNext, secondNext := first.Next, second.Next
		first.Next = second
		second.Next = firstNext
		first = firstNext
		second = secondNext
	}
}