亲宝软件园·资讯

展开

Java 重排链表

Fly upward 人气:0

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;
        }
        
 
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论