🟡 剑指 Offer II 026. 重排链表

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

用两步法找到链表中点，把后半段反转，然后逐个插入到前半段即可。

注意边界情况。（这次竟然能一次写对也是很离谱）

/** * 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) {            return;        }
        ListNode p = head, q = head;        while (q != null) {            q = q.next;            if (q != null) {                q = q.next;                p = p.next;            }        }        // 从p开始反转

        ListNode mid = p.next, nxt;        q = null;        p.next = null;        p = mid;
        while (p != null) {            nxt = p.next;            p.next = q;            q = p;            p = nxt;        }
        // q 是后半段头        p = head;        while (q != null) {            nxt = p.next;            p.next = q;            q = q.next;            p.next.next = nxt;            p = nxt;        }    }}