[Java] 2 pointer, O(n), non-recursive


  • 0
    G
    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode dummy = new ListNode(Integer.MIN_VALUE);
            ListNode slow = dummy;
            while (head != null) {
                slow.next = head;
                head = head.next;
                while ((head != null) && (head.val == slow.next.val)) head = head.next;
                slow = slow.next;
                slow.next = null;
            }
            return dummy.next;
        }
    }

  • 0
    G

    The value of "dummy" node is ignored. It can also be 0:

    ListNode dummy = new ListNode(Integer.MIN_VALUE);

  • 0
    X

    it is not one pointer and should not use nested while loop


  • 0
    G

    Thanks for pointing out. Changed it to "2 pointers".

    Even with the nested while loop, time complexity should still be O(n)


Log in to reply
 

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