LeetCode——重排链表

NO.143 重排链表中等

题目的意思是将链表按照[头 -> 尾 -> 头 -> 尾 -> 头 -> 尾 -> 头 -> 尾。。。]这样的顺序重新进行排序。

思路一：转化成数组 如果链表可以随机访问那么问题就简单了，只需要按照[0 -> length-1 -> 1 -> length-2 -> 。。。 -> mid]这样的顺序访问就好了。所以用 ArrayList 存储每个链表节点，赋予其随机访问的能力。然后双指针重新排序即可。

public void reorderList(ListNode head) {
    if (head == null) return;
    //存入数组
    ArrayList<ListNode> list = new ArrayList<>();
    ListNode p = head;
    while (p != null) {
        list.add(p);
        p = p.next;
    }
    //双指针重排
    int i = 0, j = list.size() - 1;
    while (i < j) {
        list.get(i).next = list.get(j);
        i++;
        list.get(j).next = list.get(i);
        j--;
    }
    //新的表尾节点
    list.get(i).next = null;
}

时间复杂度：O(n) 两次遍历。

空间复杂度：O(n)

思路二：翻转一半 先将链表拆成两半；将后半点链表翻转；依次逐个连接两个链表。

输入链表如下：

快慢指针找中点，分成两个链表：

翻转第二个链表：

依次逐个连接两个链表：

这些算法都在之前的题目中使用过。

public void reorderList(ListNode head) {
    if (head == null) return;
    //快慢指针找中点,O(logn)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    //拆成两个链表
    ListNode head2 = slow.next;
    slow.next = null;
    //翻转第二个链表
    head2 = reverse(head2);
    //依次逐个节点连接两个链表
    while (head2 != null) {
        ListNode next2 = head2.next;
        head2.next = head.next;
        head.next = head2;
        head = head2.next;
        head2 = next2;
    }
}

private ListNode reverse(ListNode head) {
    if (head == null) return null;
    ListNode pre = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

时间复杂度：O(n) 快慢指针O(n) + 翻转链表O(n) + 连接链表O(n)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.143 重排链表 中等

NO.143 重排链表中等