java - 删除所有右侧具有更大价值的节点（链表）

Question

给定一个单链表，删除所有右侧具有较大值的节点。这不是家庭作业，在一次采访中被问到。

例如

输入：

2--->4--->2--->1--->3--->0

那么输出应该是

4--->3--->0。

输入：

30--->40--->50--->60

那么输出应该是

60

我的方法如下：

1. reverse the link list
2. maintain the max value if the current node is less than max than remove else move next
3. reverse again

但是面试官让我优化这个。我认为他期待与@Trying 提到的相同。

Answer 1

时间复杂度 O(N)。如果您有任何疑问，请告诉我。谢谢。

Node delete(Node n){
        if(n==null){
            return null;
        }
        Node t = delete(n.next);
        if(t==null){
            return n; // i.e. right most node so just return this
        }
        else{
            Comparable c = (Comparable)n.k;
            if(c.compareTo((Comparable)t.k)<0){ //no need of this node so return t.
                return t;
            }
            else{
                n.next=t; //valid node so change the next pointer of current node
                return n;
            }
        }
    }

Answer 2

拆分问题，借用解决方案。

decreasingList(List list) {
    if list empty then return empty

    List restSolution = decreasingList(list.next)
    ... list.first ... // What now

问问自己，拥有restSolution和list.first应该返回什么。

这使得计算机科学比数学更有趣：懒惰、只做一点、委派工作。

---

抱歉以为这是作业

static class List {
    int value;
    List next;

    List(int value, List next) {
        this.value = value;
        this.next = next;
    }

    static List makeList(int... values) {
        List list = null;
        List tail = null;
        for (int value: values) {
            List node = new List(value, null);
            if (tail == null) {
                list = node;
            } else {
                tail.next = node;
            }
            tail = node;
        }
        return list;
    }

    @Override
    public String toString() {
        if (next == null) {
            return String.valueOf(value);
        }
        return String.valueOf(value) + "-->" + next.toString();
    }
}

static List decreasingList(List list) {
    if (list == null) {
        return null;
    }
    List rest = decreasingList(list.next);
    if (rest != null && list.value < rest.value) {
        return rest;
    }
    list.next = rest;
    return list;
}

public static void main(String[] args) {
    List list = List.makeList(2, 4, 2, 1, 3, 0);
    System.out.println("List: " + list);
    list = decreasingList(list);
    System.out.println("Decreasing: " + list);
}

递归可能会被解决，就像您所做的那样：通过遍历下一个节点并将下一个节点更改为前一个节点来反转。然后在尾部返回。

static List decreasingList(List list) {
    List prior = null;
    while (list != null) {
        List next = list.next;
        list.next = prior;
        prior = list;
        list = next;
    }
    list = prior; // The reversed list.

    prior = null;
    while (list != null) {
        List next = list.next;
        list.next = prior;
        if (prior == null || list.value > prior.value) {
            prior = list;
        }
        list = next;
    }
    list = prior;
    return list;
}