每日算法 #143 重排链表

#数据结构  #编程 

143.重排链表#

描述#

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

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

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

示例 1：

img

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

img

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

核心思想#

先找到后半链表头，反转后半链表，再遍历前半部分，间隔插入后半链表

相当于：查找中间节点+反转链表+插入链表

代码#

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
	}

	secondHalf := slow.Next
	slow.Next = nil
	secondHalf = reverseList(secondHalf)

	firstHalf := head
	for secondHalf != nil {
		temp1 := firstHalf.Next
		temp2 := secondHalf.Next

		firstHalf.Next = secondHalf
		secondHalf.Next = temp1

		firstHalf = temp1
		secondHalf = temp2
	}
}

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		nxt := cur.Next
		cur.Next = pre
		pre = cur
		cur = nxt
	}
	return pre
}