【力扣】重排链表

一、题目描述

题目链接： . - 力扣（LeetCode）

二、解题思路

1. 找到链表的中间节点，将链表分为两部分（可使用快慢双指针）
2. 将后半部分链表逆序（双指针或头插法）
3. 合并两个链表

一定要注意给分开之后的两个链表的末尾节点 .next 置为 null，否则会出错（超出时间限制）！

三、代码

class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return;
        }
        //1、找到链表的中间节点
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时slow所指即为中间节点
        //将原始链表分为两个链表,要注意给分开之后的两个链表的末尾节点.next置为空
        //2、逆序slow之后的部分（双指针）
        ListNode prev = slow.next;
        slow.next = null;
        ListNode cur = prev.next;
        prev.next = null;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        //逆序之后，prev指向逆序后链表的首节点
        //3、合并两个链表
        ListNode cur1 = head, cur2 = prev;
        ListNode ret = new ListNode(0);
        ListNode ccur = ret;
        while(cur1 != null) {
            ccur.next = cur1;
            ccur = cur1;
            cur1 = cur1.next;
            if(cur2 != null) {
                ccur.next = cur2;
                ccur = cur2;
                cur2 = cur2.next;
            }
        }
    }
}