问答

当前位置
  • 首页
  • 问答
  • 98. Sort List 快速排序解法 几个问题

98. Sort List 快速排序解法 几个问题

  • Ta: 九章管理员

三个问题:

1.我写了一下用链表里任意一个元素作为基准数的解法(相比原答案主要用findRandomPivot函数替代了原来的findMedian)。完整代码https://docs.google.com/document/d/1lNUdhnfbFlwFLcvP8gdXZYLDppJn9SkhNHn0IJdAPYk/edit?usp=sharing 。助教老师们可以帮忙看一下这个函数有没有可以优化的地方吗,比如现在每次调用这个函数都要先耗时O(n)遍历一遍整个链表取长度,有没有办法用O(1)时间取得呢?

private ListNode findRandomPivot(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        int index = (int)(Math.random() * length) - 1;
        System.out.println(index);
        while (index >= 0) {
            head = head.next;
            index--;
        }
        return head;
    }

2.官方快排解法version2里面sortList函数里面可以只用两个链表来划分原问题吗?即把答案的left mid right三个链表分为 left right (right含等于)。理论上貌似能make sense,我尝试写了一下代码,但是一只栈溢出错误。助教老师们能帮忙看看是哪里出bug了,还是这压根不是行得通的解法呢?

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode middle = findMiddle(head);
        ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
        // ListNode midDummy = new ListNode(0), midTail = midDummy;
        ListNode rightDummy = new ListNode(0), rightTail = rightDummy;

        while (head != null) {
            if (head.val < middle.val) {
                leftTail.next = head;
                leftTail = leftTail.next;
            // } else if (head.val == middle.val) {
            //     midTail.next = head;
            //     midTail = midTail.next; 
            } else {
                rightTail.next = head;
                rightTail = rightTail.next;
            }
            head = head.next;
        }

        leftTail.next = null;
        // midTail.next = null;
        rightTail.next = null;

        ListNode left = sortList(leftDummy.next);
        ListNode right = sortList(rightDummy.next);

        // return concat(left, midDummy.next, right);
        return concat(left, right);
    }

//    private ListNode concat(ListNode left, ListNode middle, ListNode right) {
    private ListNode concat(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0), tail = dummy; 

        tail.next = left;
        tail = getTail(tail); 

        // tail.next = middle;
        // tail = getTail(tail); 

        tail.next = right;
        tail = getTail(tail); 

        return dummy.next;
    }

    private ListNode getTail(ListNode node) {
        if (node == null) { 
            return null;
        }
        while (node.next != null) {
            node = node.next;
        }
        return node;
    }

    private ListNode findMiddle(ListNode head) {
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
  1. 关于version2官方解法里concat函数的一些问题:
    1). 首先getTail函数应该不用特判输入的ListNode是否为null,因为不可能,刚开始传进去的dummy不是null,之后传进去的为左中右子链表每一段的非空的尾结点,所以也不可能null,对吗?
    2). 然后在第119行的tail = getTail(tail);这句应该是不需要写的,因为此时我们已经把左段连上了中段,也把中段连上了后段,但是我们不需要知道后段的尾结点在哪,因为后面没有再要连的段了,对吗?
    3). concat这里应该可以直接把left,middle,right链表传进去getTail函数,而不用传另外一个引用tail,只需加一个null check即可。因为原来的左中右链表的头结点在getTail里面作为行参,原来的值并没有被改变。所以我这样写可以吗?
private ListNode concat(ListNode left, ListNode middle, ListNode right) {        
        ListNode dummy = new ListNode(0), tail = dummy; 

        if (left != null) {
            tail.next = left;
            tail = getTail(left);
        }
        if (middle != null) {
            tail.next = middle;
            tail = getTail(middle);
        }
        if (right != null) {
            tail.next = right;
            tail = getTail(right);
        }

        return dummy.next;
    }

1 个回复

2019-09-20 九章算法助教团队

1.判断出一个链表的长度后,找到中间分割位置,然后获得前一段长度,作差获得后一段长度直接传入。
2.这个是因为像0->-1->2->null这种数据按照你的划分,还会划分在同一个right段内,这样无限递归导致爆栈
3.可以,但是判断是否为空是一个良好习惯,而且省去考虑判断有没有可能为空的情况;对的;可行的

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1