Java关于重排链表详细解析
短信预约 -IT技能 免费直播动态提醒
1.题目
给定一个单链表 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;
}
}
}到此这篇关于Java关于重排链表详细解析的文章就介绍到这了,更多相关Java 重排链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
