Leetcode日记—143.reorder List

发布于 2020-10-21  115 次阅读


题目如下:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

思路:

方法一:

我一开始想着使用双向链表或者队列,这样双指针,一个从尾部开始遍历,一个从头部开始遍历,重新构建链表即可。

但是仔细一想,使用双向数据结构,本身空间复杂度就已经提升到O(n)了,而空间是为了换取时间。既然是为了快速查询,我们可以直接把节点值存入可随机存取的结构—数组中。这样可以做到按照下标快速查询。

如何再按照下标规律,每次把i与n-i依次连接起来就可以。

代码如下:

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二:

可以观察到,新得到的结果是前半段和倒置的后半段链表一次新构建的链表,因此我们可以:

1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步,将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6

第二步,将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4

第三步,依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4

第一步,leetcode有这道题。可以使用快慢指针找中点。快指针一次走两步,慢指针一次一步。这样无论总结点数为奇数还是偶数,当快指针的next为null或者快指针的next.next为null时慢指针正好到达了中点。

第二步,使用一前一后两个指针迭代就可以完成。

第三步,使用双指针重构链表就可以了。

代码如下:

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) {
        return;
    }
    //找中点,链表分成两个
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode newHead = slow.next;
    slow.next = null;
    
    //第二个链表倒置
    newHead = reverseList(newHead);
    
    //链表节点依次连接
    while (newHead != null) {
        ListNode temp = newHead.next;
        newHead.next = head.next;
        head.next = newHead;
        head = newHead.next;
        newHead = temp;
    }

}

private ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode tail = head;
    head = head.next;

    tail.next = null;

    while (head != null) {
        ListNode temp = head.next;
        head.next = tail;
        tail = head;
        head = temp;
    }

    return tail;
}

作者:windliang
链接:https://leetcode-cn.com/problems/reorder-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-34/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法三:

递归实现。

我们递归时返回当前的head,然后外层的head的next变为外层的tail,tail的next变为上一层函数的返回值。

那我们再来考虑一下函数的终止条件。若节点是单数个,则最终会剩下一个最中间的节点,那么把这个节点的next设为null,同时返回这个节点就可以了;若节点数为偶数个,则会剩下两个节点,把这时的head.next变为新的head ,新head的next为原head,原head的next设为null。

代码如下:

public void reorderList(ListNode head) {

    if (head == null || head.next == null || head.next.next == null) {
        return;
    }
    int len = 0;
    ListNode h = head;
    //求出节点数
    while (h != null) {
        len++;
        h = h.next;
    }

    reorderListHelper(head, len);
}

private ListNode reorderListHelper(ListNode head, int len) {
    if (len == 1) {
        ListNode outTail = head.next;
        head.next = null;
        return outTail;
    }
    if (len == 2) {
        ListNode outTail = head.next.next;
        head.next.next = null;
        return outTail;
    }
    //得到对应的尾节点,并且将头结点和尾节点之间的链表通过递归处理
    ListNode tail = reorderListHelper(head.next, len - 2);
    ListNode subHead = head.next;//中间链表的头结点
    head.next = tail;
    ListNode outTail = tail.next;  //上一层 head 对应的 tail
    tail.next = subHead;
    return outTail;
}

作者:windliang
链接:https://leetcode-cn.com/problems/reorder-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-34/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)