🌕 143. 重排链表

难度: 🌕

问题描述

---

解法

/**
 * 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) {
        // 思路：
        // 快慢找到链表偏左中点，和后面的节点拆分
        // 后半段链表反转
        // 双指针重新拼接成 res
        // 特殊情况特判
        if(head.next == null) {
            return;
        }
        // 快慢指针找偏左中点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        slow.next = null;
        right = mySol(right);
        ListNode left = head;
        // 在 left 中插入 right
        while(right != null) {
            ListNode next = left.next; // 暂存后一个节点
            left.next = null;
            left.next = right;
            left = right;
            right = right.next; // right 后移到下一个节点处
            left.next = next;
            left = next;
        }
    }

    private ListNode mySol(ListNode head) {
        // 特殊情况特判
        if(head == null || head.next == null) {
            return head;
        }
        // 节点数 > 1
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

---

输出