Jan 23 - Remove Duplicates From Sorted List II

拼搏现实的明天。 2021-10-24 04:52 97阅读 0赞

First we need to get the head node, use a boolean value to mark whether we find a new head or not. When we traverse the linked list,

if(cur.val != cur.next.val && flag)\{  
newHead = cur;  
flag = false;  
\}

Once we find the first non-duplicative node, set that node to be head, and flag is false, meaning that we already find the head node, no need to find a new head anymore.

Use a pointer to record the previous node that ahead of the duplicative nodes, use the while loop

while(cur != null && cur.next != null && cur.val == cur.next.val) cur = cur.next;

to get the last node of the duplicative nodes. Then the cur = cur.next; can find the first node after the duplicative nodes, let prev.next = cur.

after the while loop, we need to check whether we already find a new head. If not, set the current node(maybe null) to be the head.

Code:

/**
     * 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 cur = head;
            ListNode prev = head;
            ListNode newHead = head;
            boolean flag = true;
            while(cur != null && cur.next != null){
                if(cur.val != cur.next.val && flag){
                    newHead = cur;
                    flag = false;
                }
                if(cur.val != cur.next.val) prev = cur;
                while(cur != null && cur.next != null && cur.val == cur.next.val) cur = cur.next;
                cur = cur.next;
                prev.next = cur;
            }
            if(flag) return cur;
            return newHead;
        }
    }

转载于:https://www.cnblogs.com/5683yue/p/5154512.html