給定一個(gè)單鏈表 L 的頭節(jié)點(diǎn) head ，單鏈表 L 表示為：

L0 → L1 → … → Ln-1 → Ln
請(qǐng)將其重新排列后變?yōu)椋?/p>

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例 1:

輸入: head = [1,2,3,4]
輸出: [1,4,2,3]

示例 2:

輸入: head = [1,2,3,4,5]
輸出: [1,5,2,4,3]

提示：
鏈表的長(zhǎng)度范圍為 [1, 5 * 104]
1 <= node.val <= 1000

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/LGjMqU
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路及方法

用線性表按序存儲(chǔ)每一個(gè)節(jié)點(diǎn)，然后用雙指針鏈接是比較常規(guī)的辦法，但是會(huì)用O(n)的空間。我們采用將鏈表后半部分反轉(zhuǎn)，然后將前半部分后半部分合并即可在O(1)的空間解決。

這道題是道好題，分別寫三個(gè)子函數(shù)處理：反轉(zhuǎn)鏈表、找到鏈表中點(diǎn)、鏈表合并。這里說(shuō)下找到鏈表中點(diǎn)，使用快慢指針的方法，快指針一次走兩步，慢指針一次走一步，代碼為：

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

但是這道題要找到中點(diǎn)的前一個(gè)節(jié)點(diǎn)，因?yàn)橐焰湵淼那昂蟛糠謹(jǐn)噫?，所以代碼為：

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

整體方法為：

/**
 * 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) return;
        
        ListNode mid = findMiddleNode(head);
        ListNode head1 = head;
        ListNode head2 = mid.next;
        // 斷鏈
        mid.next = null;
        // 后半部分鏈表反轉(zhuǎn)
        head2 = reverse(head2);
        
        // 合并鏈表
        mergeList(head1, head2);
    }

    // 反轉(zhuǎn)鏈表
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;

            // 移動(dòng)指針
            prev = curr;
            curr = next;
        }

        return prev;
    }

    // 尋找鏈表中間節(jié)點(diǎn)前一節(jié)點(diǎn)，奇數(shù)長(zhǎng)度是中間鏈表，偶數(shù)長(zhǎng)度是前半部分結(jié)尾
    public ListNode findMiddleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

    // 鏈表合并
    public void mergeList(ListNode head1, ListNode head2) {
        ListNode pt1 = head1;
        ListNode pt2 = head2;

        while (pt1 != null && pt2 != null) {
            ListNode next1 = pt1.next;
            ListNode next2 = pt2.next;

            // 鏈接
            pt1.next = pt2;
            pt1 = next1;
            pt2.next = pt1;
            pt2 = next2;
        }
    }
}

結(jié)果如下：