剑指Offer(链表)-删除链表中重复的节点

  (删除链表中重复的节点)题目描述:


在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5


  解题思路:这里的重复的节点不保留是将只要重复了的节点都要删除掉,所以考虑利用哈希set的方法,先进行重复性的判断,将重复的元素加入到哈希set中去,然后将重复的元素删除。

  利用到了两个指针pre和cur,来表示前一个节点和当前节点。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        //先找出相同节点存入哈希set中
        HashSet<Integer> set = new HashSet<>();
        ListNode pre = pHead;
        ListNode cur = pHead.next;
        while(cur != null){
            if(cur.val == pre.val){
                set.add(cur.val);
            }
            pre = cur;
            cur = cur.next;
        }
        //再删除相同节点
        /**
        *删除头结点(若头结点是重复节点的话)
        */
        while(pHead!=null&&set.contains(pHead.val)){
            pHead = pHead.next;
        }
        if(pHead == null){
            return null;
        }
        /**
        *再删除中间节点
        */
        pre = pHead;
        cur = pHead.next;
        while(cur != null){
            if(set.contains(cur.val)){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return pHead;
    }
}

   (1)特别需要注意在删除头结点的时候也需要进行头结点的空判断,因为有可能前面的头结点重复了所以需要删除,但是删除之后头的部分就为空,若不进行空判断的话:

if(set.contains(pHead.val)){
      pHead = pHead.next;
}

  就有可能会出现这样的情况,重复的头结点删不掉:

         剑指Offer(链表)-删除链表中重复的节点

  所以需要的是:

while(pHead!=null&&set.contains(pHead.val)){
     pHead = pHead.next;
}
if(pHead == null){
     return null;
}

  (2)还有就是删除当前重复的元素的时候,利用的是pre.next = cur.next;,立足于当前的cur元素,因为是当前cur元素在重复集set里面,需要删除。

上一篇:【剑指offer-55】20190908/01 链表中环的入口结点


下一篇:【剑指offer-56】20190908/02 删除链表中重复的结点