Leetcode - 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 {

    // 主要思路：将链表从中间断开，对第二段进行反转，然后再合并两个链表
    // 原链表：         1 -> 2 -> 3 -> 4    |    1 -> 2 -> 3 -> 4 -> 5
    // 断成两个链表：   1 -> 2,   3 -> 4    |    1 -> 2 -> 3,   4 -> 5
    // 反转第二个链表： 1 -> 2,   4 -> 3    |    1 -> 2 -> 3,   5 -> 4
    // 合并两个链表：   1 -> 4 -> 2 -> 3    |    1 -> 5 -> 2 -> 4 -> 3
    public void reorderList(ListNode head) {

        // 节点最多两个，则无需修改
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }

        // 定义快慢指针指向开头，快指针一次移动两步，慢指针一次移动一步
        // 当快指针移到链表末尾时，慢指针指向的节点就是中间节点（或链表中心之前的一个节点）
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 如果快指针为null，说明链表有偶数个节点，此时慢指针指向的是链表中心之前的一个节点（左例中的2）
        // 如果快指针不为null，说明链表有奇数个节点，此时慢指针指向的是中间节点（右例中的3）
        // 不管是奇数个还是偶数个节点，我们都是从slow.next开始反转链表
        ListNode cur = slow.next, pre = slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 迭代完成后，pre就是反转后的链表的头节点
        ListNode cur1 = head, cur2 = pre;
        
        // 重新将两个链表连接起来
        do {
            ListNode next1 = cur1.next, next2 = cur2.next;
            cur1.next = cur2;
            cur2.next = next1;
            cur1 = next1;
            cur2 = next2;
        } while (cur2 != null);
    }
}