82. Remove Duplicates from Sorted List II

阳光穿透心脏的1/2处 2022-06-13 08:18 147阅读 0赞

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,  
Given `1->2->3->3->4->4->5`, return `1->2->5`.

Given `1->1->1->2->3`, return `2->3`.

问题描述：给定一个有序链表，删除所有有重复数字的结点，只保留原始链表中不重复的数字。

分析：该题和[83. Remove Duplicates from Sorted List][]类似，只不过要去掉所有重复的数字，而不会保留。新增一个虚拟头结点feakHead指向head；变量cur表示指针当前所指的链表位置；变量prev.next始终指向cur所在的位置，当cur!=null时循环链表，判断cur.next是否为空且cur.val与cur.next.val是否相等。若同时满足这两个条件则cur指针后移，直到不满足条件。不满足条件后判断prev.next==cur是否成立，若成立则说明cur.val与cur.next.val不相等，即cur.val没有重复，只需将prev、cur指针后移即可；若不成立则说明cur.val与cur.next.val相等，即cur.val有重复，都需要从链表中移除，只需将prev.next=cur.next，cur指针后移，然后继续循环链表。最后返回值注意应是feakHead.next.

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
            fakeHead.next = head;
            ListNode cur = head;
            ListNode prev = fakeHead;
            while( cur != null){
                while (cur.next != null && cur.val == cur.next.val) { 
                    cur = cur.next;
                }
                if (prev.next == cur) 
                    prev = prev.next;
                else 
                    prev.next = cur.next;
                cur = cur.next;
            }
            return fakeHead.next;
        }
    }

[83. Remove Duplicates from Sorted List]: http://blog.csdn.net/wust_lh/article/details/73928234