链表系列一＞重排链表

题目：

链接: link

这里是引用

解析：

在这里插入图片描述

细节：

在这里插入图片描述

代码：

代码语言：javascript代码运行次数：0运行复制

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //边界
        if (head == null || head.next == null || head.next.next == null) return;

        ListNode fast = head,slow = head;

        //1.找链表的中间节点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //2.把 slow 后面的部分链表给逆序 - 头插法
        ListNode prev = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;//把两个链表断开

        while(cur != null){
            //记录cur后的节点，不然后面就断开了
            ListNode next = cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = next;
        }

        //3.合并两个链表(第一个头--》head, 第二个的头--》prev)
        ListNode tmp = new ListNode(0);
        ListNode cur1 = head,cur2 = prev.next;
        ListNode curN = tmp;

        while(cur1 != null){
            curN.next = cur1;
            curN = cur1;
            cur1 = cur1.next;

            if(cur2 != null){
                curN.next = cur2;
                curN = cur2;
                cur2 = cur2.next;
            }
        
        }
    }
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-27，如有侵权请联系 cloudcommunity@tencent 删除前往查看public链表classintnull