143.M 重排链表

Problem: 143. 重排链表

思路

1. 找到链表的中间节点

2. 反转后半部分（从mid.Next开始），同时从mid节点处断开为两截

3. 拼接两个链表

Code

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

	// 找到中间节点
	mid := findMid(head)
	// 反转后半部分
	l2 := reverse(mid.Next)
	//把链表中mid节点处断开
	mid.Next = nil

	// 合并两个链表
	merge(head, l2)
}

func merge(l1 *ListNode, l2 *ListNode) {
	for l1 != nil && l2 != nil {
		l1Next := l1.Next
		l2Next := l2.Next

		l1.Next = l2
		l2.Next = l1Next

		l1 = l1Next
		l2 = l2Next
	}
}

func reverse(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	return pre
}

func findMid(head *ListNode) *ListNode {
	slow, fast := head, head
	// 注意这里的判空条件是要确保fast.Next.Next也不为空
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow
}