删除链表的重复元素

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

解题思路:使用快慢指针的方式,让slow指针在fast指针前一个节点,fast遍历到next节点为重复元素时,则进入循环遍历至没有不重复元素,将slow节点的next指针指向该节点。

但有特殊情况,当第一个节点也为重复元素时,我们需要判断slow节点的值是否为fast节点的值,如果是则证明第一个节点也为重复元素,需要删除。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if(fast == null)
            return head;
        while(fast != null && fast.next != null){
            //找到重复的节点
            if(fast.val == fast.next.val){
                //直到没有重复的节点
                while(fast.next != null && fast.val == fast.next.val){
                    fast = fast.next;
                } 
                //如果slow是第一个节点,此时应该将头节点更新为不重复的第一个节点
                if(slow.val == fast.val){
                    slow = fast.next;
                    head = slow;
                }else{
                    slow.next = fast.next;
                }
                fast = fast.next;
                continue;
            }
            //slow节点为fast节点的前一个节点,用于删除重复的节点 
            slow = fast;
            fast = fast.next;
        }
        return head;
    }
}


版权声明:本文为weixin_46015737原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。