链表（篇2）删除右侧有更大值的节点

本文主要是介绍链表（篇2）删除右侧有更大值的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个单链表，删除右侧有更大值的所有节点。
示例：
a）列表12-> 15-> 10-> 11-> 5-> 6-> 2-> 3-> NULL应该更改为15-> 11-> 6-> 3-> NULL。请注意，12，10，5和2已被删除，因为在右侧有一个更大的值。

当我们检查12，我们看到12之后有一个节点的值大于12（即15），所以我们删除12.
当我们检查15，我们发现没有15之后的值大于15的节点，所以我们保持这个节点。
当我们这样去，我们得到15-> 6-> 3

b）列表10-> 20-> 30-> 40-> 50-> 60-> NULL应该更改为60-> NULL。注意，10,20,30,40和50已被删除，因为它们在右侧都具有更大的值。

c）不应改变列表60-> 50-> 40-> 30-> 20-> 10-> NULL。

解法1（简单）

使用两个循环。在外层循环中，逐个选择链表的节点。在内部循环中，检查是否存在其值大于所选节点的节点。如果存在其值较大的节点，则删除所选节点。
时间复杂度：O（n ^ 2）
代码：

public static ListNode Sort(ListNode head){ListNode phead=new ListNode(0);ListNode pre=head,q,next;next=phead;while(pre!=null){q=pre.next;while(q!=null&&(q.val<=pre.val)){q=q.next;}if(q==null){next.next=pre;next=next.next;}pre=pre.next;}return phead.next;}

解法2（使用反转）

1.反转列表。
2.移动反转列表。保持当前节点值最大为Max。如果下一个节点<max，则删除下一个节点，否则max =下一个节点。
3.再次颠倒列表以保留原始顺序。时间复杂度：O（n）

代码

public static ListNode Sort(ListNode head,int tag){int Max=0;head=ReverseList(head);ListNode Current;Current=head;if(Current==null)return null;else {Max=Current.val;}while(Current!=null&&Current.next!=null){if(Current.next.val>=Max){Max=Current.next.val;Current=Current.next;}else {Current.next=Current.next.next;}}head=ReverseList(head);return head;}