Java关于重排链表详细解析

Java关于重排链表详细解析

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 = nhttp://ode;

while (l1 != null) {

ListNode next1 = prev.next;

ListNode next2 = l1.next;

prev.next = l1;

l1.next = next1;

prev = next1;

l1 = next2;

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。