题目描述

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

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

1626420311-PkUiGI-image.png

示例 2：

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

1626420320-YUiulT-image.png

提示：

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

思路

转换为线性表

因为链表的访问只能是线性的，无法随机访问，所以可以先将链表转换为线性表，然后再根据线性表的长度，通过下标来重新排列链表。这样就可以避免链表的访问时间复杂度为 O(n) 的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reorderList(head *ListNode) {
	nodes := make([]*ListNode, 0)
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}

	nodes_len := len(nodes)
	for i := 0; i < nodes_len/2; i++ {
		nodes[i].Next = nodes[nodes_len-i-1]
		nodes[nodes_len-i-1].Next = nodes[i+1]
	}

    nodes[nodes_len/2].Next = nil
}

代码实现也是比较简单的：

  • 先遍历链表，将每个节点存入线性表中
  • 然后根据线性表的长度，将后面的节点插入到前面的节点中
  • 最后将最后一个节点的 next 指针置为 nil，避免出现环形链表

查找中间点 + 反转链表 + 合并链表

中间点查找

中间点的查找可以使用快慢指针的方法，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针正好在中间节点。书接上文 876. 链表的中间结点

1
2
3
4
5
6
7
func middleNode(head *ListNode) *ListNode {
	for fast := head; fast != nil && fast.Next != nil; fast = fast.Next.Next {
		head = head.Next
	}

	return head
}

反转链表

反转链表可以使用迭代的方法，遍历链表，将当前节点的 next 指针指向前一个节点，然后将当前节点赋值为前一个节点，直到遍历完整个链表。书接上文 206. 反转链表

1
2
3
4
5
6
7
8
9
10
func reverseList(head *ListNode) (res *ListNode) {
	for head != nil {
		next := head.Next
		head.Next = res
		res = head
		head = next
	}

	return
}

合并链表

目前已经完成了中间点的查找和反转链表的实现，接下来需要实现合并链表的功能。在合并链表时，用两个指针分别指向两个链表的头节点，然后依次将节点添加到新的链表中。

需要注意的是，在合并链表的时候，仍然需要考虑原链表的长度的奇数和偶数的情况。

  • 原链表长度为偶数时，比如 1->2->3->4->5->6，在经过中间点查找与后半部分反转后，链表变为 1->2->3->4 和 6->5->4，合并时需要将 1->2->3->4 和 6->5->4 进行合并，最终得到的链表为 1->6->2->5->3->4。
  • 原链表长度为奇数时，比如 1->2->3->4->5，在经过中间点查找与后半部分反转后，链表变为 1->2->3 和 5->4->3，合并时需要将 1->2->3 和 5->4->3 进行合并，最终得到的链表为 1->5->2->4->3。

这里其实有一个隐含的坑，就是前面的中间点查找算法中，奇数长度的链表返回的是中间节点，而偶数长度的链表返回的是后半部分的第一个节点。所以这会导致后面要合并的两个链表的长度不一致，并且要合并的两个链表的尾节点是同一个节点。合并的时候要注意特殊处理尾节点，不然会导致尾节点的 next 指针指向自己，从而形成环形链表。

这里一种方法是在合并结束后将尾节点的 next 指针置为 nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reorderList(head *ListNode) {
	firstPointer := head
	secondPointer := reverseList(middleNode(head))
	for firstPointer != nil && secondPointer != nil {
		nextFirst := firstPointer.Next
		nextSecond := secondPointer.Next

		firstPointer.Next = secondPointer
		secondPointer.Next = nextFirst

		firstPointer = nextFirst
		secondPointer = nextSecond
	}

    // 处理尾节点
    if firstPointer != nil && firstPointer.Next != nil {
        firstPointer.Next = nil
    }
}

上面的代码中，firstPointer 和 secondPointer 分别指向两个链表的头节点，然后依次将节点添加到新的链表中。在原链表的长度为偶数时，由于中间节点有两个，并且没有断开两个中间节点之间的连接，所以在合并的时候会导致两个链表的长度不一致。以 1->2->3->4->5->6 为例，经过中间节点查找与后半部分反转后，链表变为 1->2->3->4 和 6->5->4，逐个添加节点后，当进行到第三次归并的时候：

  • firstPointer 指向 3，secondPointer 指向 4
  • 这个时候代码逻辑仍然会把第二个链表中 secondPointer 指向的节点（x: 4）添加到 firstPointer 指向的节点（y: 3）后面（firstPointer.Next = secondPointer 3->4）
  • 再将 firstPointer 节点（y: 3）的后续节点(也是 x:4 )添加到 secondPointer 指向的节点（x: 4）后面（secondPointer.Next = nextFirst 3->4->4）
  • 这样就导致了错误，如果文字描述不清楚，可以画图理解一下。

所以上面的代码最后特别处理一下尾节点，避免出现环形链表。

1
2
3
if firstPointer != nil && firstPointer.Next != nil {
    firstPointer.Next = nil
}

上面的分析会发现，其实出问题的地方在于处理尾节点的时候，也就是 firstPointer.Next 和 secondPointer 指向同一个节点的时候，secondPointer 重复添加导致的链表错误，而由于 firstPointer 的尾节点其实已经包括了 secondPointer 的尾节点，所以在合并的时候，当遇到 firstPointer.Next 和 secondPointer 指向同一个节点的情况时直接退出循环，不再进行合并操作，这样就可以避免出现环形链表的问题。

这样就可以把上面的代码简化一下，直接在合并的时候判断 firstPointer.Next 和 secondPointer 是否相等，如果相等则说明已经到达了尾节点，可以直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reorderList(head *ListNode) {
	firstPointer := head
	secondPointer := reverseList(middleNode(head))
	for firstPointer != nil && secondPointer != nil && firstPointer.Next != secondPointer {
		nextFirst := firstPointer.Next
		nextSecond := secondPointer.Next

		firstPointer.Next = secondPointer
		secondPointer.Next = nextFirst

		firstPointer = nextFirst
		secondPointer = nextSecond
	}
}

进一步细想，其实如果原链表的长度为奇数时，firstPointer 和 secondPointer 的节点时一样的，这个时候按照代码逻辑去添加也不会导致环形链表的问题，但如果直接退出循环也不会影响结果，所以可以直接将 firstPointer 和 secondPointer 指向同一个节点的情况也加入到循环条件中也不会出问题，并且因为firstPointer 和 secondPointer 的尾节点只会出现两种情况：

  • 原链表的长度为偶数时，当 secondPointer 到达尾节点时，firstPointer.Next 和 secondPointer 指向同一个节点，这个时候需要退出循环。
  • 原链表的长度为奇数时，当 firstPointer 和 secondPointer 会同时到达各自的尾节点，并且此时 firstPointer 和 secondPointer 一定指向同一个节点，这个时候也需要退出循环。

所以可以进一步简化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reorderList(head *ListNode) {
	firstPointer := head
	secondPointer := reverseList(middleNode(head))
	for firstPointer != secondPointer && firstPointer.Next != secondPointer {
		nextFirst := firstPointer.Next
		nextSecond := secondPointer.Next

		firstPointer.Next = secondPointer
		secondPointer.Next = nextFirst

		firstPointer = nextFirst
		secondPointer = nextSecond
	}
}