剑指offer-- 链表中环的入口结点(Java)

题目:在一个排序的链表中,如何删除重复的结点?

思路:
  设置一个preNode,用于记录当前结点的前一个结点,如果当前结点和后一结点的值相同(记该值为dupVal),通过循环往后找到第一个不为dupVal的结点,把该结点设置为当前结点,并赋值给preNode.next,即相当于完成了删除操作;而当前结点和后一结点的值不相同时,把当前结点和preNode往后移一位即可。    

实现:

public ListNode deleteDuplication(ListNode pHead)
    {
        if (pHead == null || pHead.next == null) return pHead;
        ListNode curNode = pHead;
        ListNode preNode = null;
        while(curNode!=null){
            if(curNode.next!=null && curNode.val == curNode.next.val){
                ListNode delete = curNode;
                int dulpValue  = curNode.val;
                while(delete!=null && delete.val == dulpValue){
                    delete = delete.next;
                }
                if(preNode == null){
                    pHead = delete;
                }else{
                    preNode.next = delete;
                }
                curNode = delete;
            }else{
                preNode = curNode;
                curNode = curNode.next;
            }
        }
        return pHead;
    }

收获:

  1. 删除多个结点时,只要把重复结点前一个结点的next指向重复结点的后一个结点;
  2. 不要把重复结点一个一个删除,先定义一个确定当前结点是否重复,然后按上一句话的方法进行删除即可。
  3. 注意如果头结点与之后节点重复时,对于preNode的处理
上一篇:复杂链表的复制


下一篇:在一个排序的列表中,存在重复的节点,删除该链表中重复的节点,重复的节点不保存,返回链表头指针