重排链表（143）

题目

给定一个单链表 L：L0 → L1 → … → Ln-1 → Ln ， 将其重新排列后变为： L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

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

示例

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

算法

• 使用快慢指针来找到链表中点，并将链表分为两个链表
• 将后半边链表反转
• 将后半边链表依次插入在前半边链表的间隔中

如果链表为偶数个节点，那么前后两个链表的节点数相同；如果链表为奇数个节点，那么后半边链表会比前半边链表多一个节点，所以我们在插入结束后需要判断后半边链表是否还有剩余节点，如果有我们要将其放在最后结果链表的最后面

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const reorderList = (head) => {
	if (!head || !head.next) return head;
	// 寻找中点，分隔链表
	let fast = head;
	let slow = new ListNode();
	slow.next = head;
	while (fast && fast.next) {
		fast = fast.next.next;
		slow = slow.next;
	}
	let mid = slow.next;
	slow.next = null;
	// 反转后半部分链表
	const recursion = (node) => {
		if (!node.next) return node;
		let reverseHead = recursion(node.next);
		node.next.next = node;
		node.next = null;
		return reverseHead;
	};
	// 将后半部分插入到前半部分
	let frontNode = head;
	let reverseNode = recursion(mid);
	while (frontNode.next && reverseNode.next) {
		const insertedNode = reverseNode;
		const insertedNextNode = frontNode.next;
		reverseNode = reverseNode.next;
		frontNode.next = insertedNode;
		insertedNode.next = insertedNextNode;
		frontNode = frontNode.next.next;
	}
	if (reverseNode) frontNode.next = reverseNode;
	return head;
};