Clean Java solution using doubly linked list


  • 0
    I
    class Solution {
        public int[] asteroidCollision(int[] a) {
            Node head = new Node(0);
            Node tail = new Node(0);
            Node iter = head;
            for (int i = 0; i < a.length; i++) {
                iter.next = new Node(a[i]);
                iter.next.prev = iter;
                iter = iter.next;
            }
            iter.next = tail;
    
            // remove
            iter = head.next;
            while (iter != tail && iter.next != tail) {
                if (iter.val > 0 && iter.next.val < 0) {
                    int sum = iter.val + iter.next.val;
                    Node next, prev;
                    if (sum == 0) {
                        prev = iter.prev;
                        next = iter.next.next;
                    } else if (sum > 0) {
                        next = iter.next.next;
                        prev = iter;
                    } else {
                        next = iter.next;
                        prev = iter.prev;
                    }
                    prev.next = next;
                    next.prev = prev;
                    iter = prev;
                } else {
                    iter = iter.next;
                }
            }
    
            List<Integer> res = new ArrayList<>();
            iter = head.next;
            while (iter != tail) {
                res.add(iter.val);
                iter = iter.next;
            }
            int[] resa = new int[res.size()];
            for (int i = 0; i < res.size(); i++) resa[i] = res.get(i);
            return resa;
        }
    
        private static class Node {
            int val;
            Node next, prev;
            public Node(int val) {
                this.val = val;
            }
        }
    
    }
    

  • 0
    I

    I actually find this more intuitive than the stack method for some reason lol


Log in to reply
 

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