Java clean code with stack mindset


  • 0
    H

    We can use a ListNode to simulate the top of a "stack" which only stored ordered unique elements.

    Have a cur pointer to scan this linked list and add cur to that stack if it's empty or the value of top is different from cur's.

    If cur.value == top.value, we need to iterate the list until a different element shows. At that point, we will "pop" the top, as it's a duplicate.

    public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            
            ListNode dummy = new ListNode(Integer.MAX_VALUE);
            ListNode top = dummy;
            ListNode last = top;
            ListNode cur = head;
            
            while (cur != null) {
                if (top == dummy || top.val != cur.val) {
                    top.next = cur;
                    last = top;
                    top = top.next;
                    cur = cur.next;
                } else {
                    while (cur != null && top.val == cur.val) {
                        cur = cur.next;
                    }
                    top = last;
                    top.next = null;
                }
            }
            
            return dummy.next;
        }
    

Log in to reply
 

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