lt. 0493

*493. Implement Queue by Linked List II
*单链表实现
100% test cases passedTotal runtime 2620 ms
Your submission beats 15.00% Submissions!

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int item) {
        val = item;
        next = null;
    }
}

public class Dequeue {
    public ListNode hd;
    public ListNode tl;
    public ListNode dummy;
    public Dequeue() {
        dummy = new ListNode(0);//head
        hd = dummy.next;
        tl = dummy.next;
    }

    /*
     * @param item: An integer
     * @return: nothing
     */
    public void push_front(int item) {
        ListNode tr = new ListNode(item);
        if(hd==null){//Empty queue, in fact tl is also null
            tr.next = dummy.next;
            dummy.next = tr;
            hd = tr;
            tl = tr;
        }else{//only one node
            tr.next = dummy.next;
            dummy.next = tr;
            hd = tr;
        }
    }

    /*
     * @param item: An integer
     * @return: nothing
     */
    public void push_back(int item) {
        ListNode tr = new ListNode(item);
        if(hd==null){//Empty queue, in fact tl is also null
            tr.next = dummy.next;
            dummy.next = tr;
            hd = tr;
            tl = tr;
        }else{//
            tl.next = tr;
            tl = tl.next;
        }
    }

    /*
     * @return: An integer
     */
    public int pop_front() {
        int ret = hd.val;
        if(hd==tl){//If there is only one node, hd and tl must be set null
            hd=tl=null;
            dummy.next=null;
        }else{
            dummy.next = hd.next;
            hd = dummy.next;
        }
        return ret;
    }

    /*
     * @return: An integer
     */
    public int pop_back() {
        int ret = tl.val;
        if(hd == tl){//If there is only one node, hd and tl must be set null
            hd = tl = null;
            dummy.next = null;
        }else{
            ListNode tr = dummy;
            while(tr.next!=tl){
             tr = tr.next;
            }
            tl = tr;
        }
        return ret;
    }
}

*双链表实现的
100% test cases passedTotal runtime 2620 ms
Your submission beats 15.00% Submissions!

class Node {
    public int val;
    public Node next, prev;
    public Node(int _val) {
        val = _val;
        prev = next = null;
    }
}

public class Dequeue {
    public Node first, last;
    
    public Dequeue() {
        first = last = null;
        // do initialize if necessary
    }

    public void push_front(int item) {
        // Write your code here
        if (first == null) {
            last = new Node(item);
            first = last;       
        } else {
            Node tmp = new Node(item);
            first.prev = tmp;
            tmp.next = first;
            first = first.prev;
        }
    }

    public void push_back(int item) {
        // Write your code here
        if (last == null) {
            last = new Node(item);
            first = last;       
        } else {
            Node tmp = new Node(item);
            last.next = tmp;
            tmp.prev = last;
            last = last.next;
        }
    }

    public int pop_front() {
        // Write your code here
        if (first != null) {
            int item = first.val;
            first = first.next;
            if (first != null)
                first.prev = null;
            else
                last = null;
            return item;
        }
        return -11;
    }

    public int pop_back() {
        // Write your code here
        if (last != null) {
            int item = last.val;
            last = last.prev;
            if (last != null)
                last.next = null;
            else
                first = null;
            return item;
        }
        return -11;
    }
}