My accepted Java code


  • 139
    S
    public ListNode deleteDuplicates(ListNode head) {
            if(head==null) return null;
            ListNode FakeHead=new ListNode(0);
            FakeHead.next=head;
            ListNode pre=FakeHead;
            ListNode cur=head;
            while(cur!=null){
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }
                if(pre.next==cur){
                    pre=pre.next;
                }
                else{
                    pre.next=cur.next;
                }
                cur=cur.next;
            }
            return FakeHead.next;
        }

  • 6
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    C

    pretty good .....


  • 0
    F
    This post is deleted!

  • -1
    L

    Nice solution, it seems like when you have two while loops in python, OJ will consider this as TLE automatically.
    A small modification is needed when you using python with above algorithm:

    change second 'while' to 'if' and add 'continue' after cur=cur.next


  • 0
    B

    don't need change the second while to if, no time limit error, changed it will cause wrong logic.


  • 0
    L
    This post is deleted!

  • -1
    D

    My code use no extra space, but some more control logic.
    The logic is straightforward:
    The outside loop for traverse throught the linked list, inside the loop: one for deleting duplicate nodes, the other for non-duplicate case, update the "pre".

    public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    ListNode pre = null;
    while (cur != null && cur.next != null) {
    if (cur.val == cur.next.val) { // this part is used for deleting duplicate node
    while (cur.next != null && cur.val == cur.next.val) {
    cur = cur.next;
    }
    if (pre != null) {
    pre.next = cur.next;
    } else {
    head = cur.next;
    }
    cur = cur.next;
    } else if (cur != null) { //this part is for non-duplicate node
    pre = cur;
    cur = cur.next;
    }
    }
    return head;
    }
    }


  • 0
    W

    I think the key statement is:
    if(pre.next==cur){
    pre=pre.next;
    }
    else{
    pre.next=cur.next;
    }
    When there are some elements to skip, pre->next point to curr->next. While there is no skipping, pre point to curr


  • -1
    H

    hibernate对象关系映射


  • 7
    Z

    Actually I found there is a more straightforward way to solve this problem:
    https://discuss.leetcode.com/topic/61919/o-n-time-o-1-space-easiest-understanding

    The idea is simple, we maintain two pointers, pre, cur in the given List. Pre pointer is always referring to one position before the cur pointer. When we found pre.val != cur.val && cur.val != cur.next.val, the node referred by cur pointer is a unique node.

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0 == head.val ? 1 : 0);// to guarantee the dummy node is not same as the original head.
        dummy.next = head;
        
        ListNode pre = dummy;
        ListNode cur = head;
    
        ListNode first = dummy; // the first node in the new unduplicated(result) list.
        
        while (cur != null && cur.next != null) {
            if (cur.val != pre.val && cur.val != cur.next.val) { // we found a unique node, we connect it at the tail of the unduplicated list, and update the first node.
                first.next = cur;
                first = first.next;
            }
            pre = cur;
            cur = cur.next;
        }
        
        if (pre.val != cur.val) {  // the last node needs to be dealt with independently
            first.next = cur;
            first = first.next;
        }
        
        first.next = null;  // the subsequent list is duplicate.
        
        return dummy.next;
    }

  • 0
    S

    @snowfish
    public ListNode deleteDuplicates(ListNode head) {
    if(head==null) return null;
    ListNode FakeHead=new ListNode(0);
    FakeHead.next=head;
    ListNode pre=FakeHead;
    ListNode cur=head;
    Boolean flag = false;
    while(cur!=null){

            while(cur.next!=null&&cur.val==cur.next.val){
                flag = true;
                cur=cur.next;
            }
            
            if(flag){
               cur = cur.next;
            }
            else{
                pre.next=cur;
                pre = cur;
                cur=cur.next;
            }
            
            flag = false;
        }
        pre.next = null;
        return FakeHead.next;
    }
    
    • list item

  • 0
    D

    sorry,little don't understand,if it is 1-2-2-3-3-5,will the first 3 came into the fake head?


  • 0
    L

    @DianjinLi
    pre.next will point to 3 at some point, but it won't move forward, then the pre.next will point to 5 and move to 5. "pre" only move forward when (pre.next==cur.next) is true.


  • 0
    P

    @snowfish cur might be additional, and can be replaced by head


  • 1
    P

    public ListNode deleteDuplicates(ListNode head) {
    ListNode temp=new ListNode(0);
    temp.next=head;

        ListNode sec=temp;
        
        while(sec.next!=null && sec.next.next!=null){
            if(sec.next.val==sec.next.next.val){
                int dupli=sec.next.val;
                while(sec.next!=null && sec.next.val==dupli){
                    sec.next=sec.next.next;
                }
            }
            else {
                sec=sec.next;
            }
        }
        return temp.next;
    }

  • 0
    H

    Just got confused how to identify two list node equal like "pre.next==cur"


  • 0

    Very clear solution! Thanks!


  • 0
    Y

    so smart. damn good


  • 0
    W

    you don't need the first line


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.