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

分类: IT文章 • 2024-01-03 07:46:43

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

解答：

首先我们分析下题目，一个有序的链表，如果存在节点的数字一样也会是连续的，不会出现中间出现其它数字的节点再重复。

  @Data
  public static class ListNode {
    private int val;
    private ListNode next;

    public ListNode(int val) {
      this.val = val;
    }
  }

View Code

解法1:

/*定义一个哑节点*/
    ListNode dumb = new ListNode(0);
    /*哑节点的下一个节点指向头节点*/
    dumb.next = head;
    /*定义一个指向头的节点引用*/
    ListNode tempHead = head;
    /*所有元素*/
    Set<Integer> elements = new HashSet<>();
    /*重复的元素*/
    Set<Integer> clearElements = new HashSet<>();
    /*定义一个遍历的前一个节点的引用*/
    ListNode pre = dumb;
    /*找出重复的元素并放入集合*/
    while (head != null) {
      int val = head.val;
      if (elements.contains(val)) {
        clearElements.add(val);
      }
      elements.add(val);
      head = head.next;
    }
    /*移除重复元素*/
    while (tempHead != null) {
      int val = tempHead.val;
      if (clearElements.contains(val)) {
        pre.next = tempHead.next;
        tempHead = tempHead.next;
        continue;
      }
      pre = tempHead;
      tempHead = tempHead.next;
    }
    return dumb.next;

View Code

这种解法是先遍历链表，找出重复的元素数值放入set集合中，然后再次遍历链表，如果节点的数字在set集合中出现则把这个节点删除，此种解法的时间复杂度是o(4N^2),空间复杂度是o(3n).

解法2:

public static ListNode deleteDuplicates1(ListNode head) {
    /*定义一个哑节点*/
    ListNode dumb=new ListNode(0);
    /*哑节点的下一个节点指向头节点*/
    dumb.next=head;
    /*快指针*/
    ListNode fast=head;
    /*慢指针*/
    ListNode slow=dumb;
    /*当快指针不为null时继续*/
    while (fast!=null){
      /*如果fast到了尾节点或fast的数字与fast的next的数字不一样时进入*/
      if(fast.next==null||fast.val!=fast.next.val){
        /*如果相邻，则slow引用指向fast所指的对象*/
        if(slow.next==fast){
          slow=fast;
        }else{
          /*如果不相邻，则说明中间存在重复元素，将slow的下一个指向fast的下一个，这样就抹去了相同的元素*/
          slow.next=fast.next;
        }
      }
      fast=fast.next;
    }
    return dumb.next;
  }

View Code

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

相关推荐