leetcode 143. 重排链表

题目地址：https://leetcode.cn/problems/reorder-list/

按照题意的那3步做就可以了
1、将链表分成2部分（如果是奇数个结点将中间结点作为第一个链表的一部分）
2、将第二部分结点逆转过来
3、两个链表结点穿插组成一个新的链表

使用快慢指针，定义两个指针，快指针每次跳2个结点，慢指针每次跳一个结点，快指针为空时，慢指针正好跳到中间结点。

逆转链表的实现如下：

private ListNode reverse(ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode tmp = head.next;
        head.next = newHead;
        newHead = head;
        head = tmp;
    }
    return newHead;
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode mid = findMid(head);
        ListNode l2 = mid.next;
        // 将前半部分链表截断
        mid.next = null;
        // 将后半部分链表反转
        l2 = reverse(l2);
        ListNode l1 = head;
        // 组装新的链表
        while (l1 != null && l2 != null) {
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = tmp;
            l1 = tmp;
        }
    }

    
    ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    
    ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

• 2022/05/11，逆转链表这一块想的头疼啊，想象出每一步区分指针变量，结点的指向都指向谁就好理解了