删除所有在右侧(链表)具有更大价值的节点

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;
}