Java 重排链表
Fly upward 人气:01.题目
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0→ L1 → … → Ln-1 → Ln 请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
来源：力扣（LeetCode）
2.解析
将一个链表分为两个子链表，然后将其归并。
我们要先找到链表的中间节点，在中间节点将其断开
然后反转后半链表
再将两个子链表逐个连起来
将后半链表反转，独立成一个子链表。
最后将两个子链表的节点逐个连接就OK了
3.代码
class Solution {
public void reorderList(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//找中间节点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//截断链表
ListNode cur = slow.next;
slow.next = null;
//反转后半链表
ListNode node = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = node;
node = cur;
cur = curNext;
}
//合并
ListNode prev = head;
ListNode l1 = node;
while (l1 != null) {
ListNode next1 = prev.next;
ListNode next2 = l1.next;
prev.next = l1;
l1.next = next1;
prev = next1;
l1 = next2;
}
}
}
加载全部内容