首页 > 编程语言 > 详细

82. 删除排序链表中的重复元素 II

时间:2021-08-30 13:51:25      阅读:12      评论:0      收藏:0      [点我收藏+]

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

技术分享图片

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

技术分享图片

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

删除排序链表中的重复元素II。

时间O(n)

空间O(1)

 

思路:

需要创建一个dummy节点,放在所有需要遍历的节点之前,遍历的时候,

找是否有两个节点的val相同,找到后记下这个val。

再往后遍历的时候,只要遇到这个val就跳过。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
       ListNode p=new ListNode(0);
       ListNode cur=p;
       cur.next=head;
       while(cur.next!=null && cur.next.next!=null){
           if(cur.next.val==cur.next.next.val){
               int flagVal=cur.next.val;
               while(cur.next!=null&&cur.next.val==flagVal){
                   cur.next=cur.next.next;
               }
           }else{
               cur=cur.next;
           }
       }
       return p.next;

    }
}

  

 

82. 删除排序链表中的重复元素 II

原文:https://www.cnblogs.com/iwyc/p/15202826.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!