剑指 Offer II 026. 重排链表
题目
给定一个单链表 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]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示:
- 链表的长度范围为 [1, 5 * 104]
- 1 <= node.val <= 1000
注意:本题与主站143题相同
题解
public void reorderList(ListNode head) {
// 使用快慢指针找链表中点
ListNode slow = new ListNode(0, head), fast = new ListNode(0, head);
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 待倒叙的链表
ListNode mid = slow.next;
// 顺序链表后置空
slow.next = null;
ListNode reverse = new ListNode(0), t;
// 将后半部分链表倒置
while (mid != null) {
t = mid.next;
mid.next = reverse.next;
reverse.next = mid;
mid = t;
}
// 根据题意 顺序链表肯定长度大于(节点数位奇数的时候大于)等于倒叙链表
reverse = reverse.next;
// 交叉合并两个链表
while (reverse != null) {
t = head.next;
head.next = reverse;
reverse = reverse.next;
head.next.next = t;
head = t;
}
}