143. Reorder List #

题目 #

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路 #

寻找链表中心结点 + 翻转链表 + 合并链表

代码 #

暴力解 #

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 ListNode getTail(ListNode head) {
        ListNode ptr = head;
        while (ptr.next != null && ptr.next.next != null) ptr = ptr.next;
        ListNode tail = ptr.next;
        ptr.next = null;
        return tail;
    }
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode tail = getTail(head);
        tail.next = head.next;
        head.next = tail;
        reorderList(tail.next);
    }
}

寻找链表中间结点+反转链表+合并链表 #

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 ListNode findMiddle(ListNode head) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode slow = sentinel, fast = sentinel;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode result = slow.next;
        slow.next = null;
        return result;
    }
    /** 反转链表 */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head, temp = head.next;
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = temp;
            if (temp != null) temp = temp.next;
        }
        return prev;
    }
    /** 合并链表 */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode middle = findMiddle(head);
        ListNode tail = reverseList(middle);
        ListNode ptr1 = head, ptr2 = tail;
        while (ptr1 != null && ptr2 != null) {
            ListNode newPtr1 = ptr1.next, newPtr2 = ptr2.next;
            ptr1.next = ptr2;
            ptr2.next = newPtr1;
            ptr1 = newPtr1;
            ptr2 = newPtr2;
        }
    }
}

致谢 #

灵茶山艾府