牛客网-删除链表中重复的节点

Myth丶恋晨 2023-03-01 10:14 35阅读 0赞

# 题目描述 #

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

OJ链接：[https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef][https_www.nowcoder.com_practice_fc533c45b73a41b0b44ccba763f866ef]

# 解法1 带头节点的解法 #

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    public class Solution { 
        public ListNode deleteDuplication(ListNode pHead){ 
            
            if(pHead == null)
                return pHead;
            //为了简单，构造一个有头结点的链表
            ListNode head = new ListNode(0);
            head.next = pHead;//带头节点的链表的next指向pHead，我们返回的时候就返回head.next即可
            
            //prev永远在last的前面
            ListNode prev = head;//前指针 目的：永远指向的是重复节点的前一个节点，为了方便删除
            ListNode last = prev.next;//后指针
            
            while(last!=null ){ 
                
                //1、，先找到重复的开始
                //如果last和last.next不相等，就一直让prev和last往后走
                while(last.next != null && last.val!= last.next.val){ 
                    prev = prev.next;
                    last = last.next;
                }
                
                
                //2、再找到重复的范围
                //如果last和last.next相等，就让last一直往后走,找和last.val相等的
                while(last.next != null && last.val == last.next.val){ 
                    last=last.next;
                }
                
                //走到这里，结果一共有三种情况。注意：prev永远指向的是前驱有效起始节点:
                /* 走到这里就构成了一个：(prev,last] 的区间 1、last.next != null 并且prev到last是一段重复的范围，prev.next=last.next 2、last.next == null 并且prev到last是一段重复的范围，prev.next=last.next(null) 3、last.next == null 整张链表没有重复节点 */
                
                if(prev.next != last){ 
                    prev.next = last.next;
                }
                
                //走到这一步，就是为了保证恢复和最开始一致
                last = last.next;
                
            }
            //因为要把头节点给省略，所以这样做
            return head.next;
        }
    }

[https_www.nowcoder.com_practice_fc533c45b73a41b0b44ccba763f866ef]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef