Implement Queue by Linked List(lintcode 492)

Description

Implement a Queue by linked list. Support the following basic methods:

1. enqueue(item). Put a new item in the queue.
2. dequeue(). Move the first item out of the queue, return it.

Example

enqueue(1)
enqueue(2)
enqueue(3)
dequeue() // return 1
enqueue(4)
dequeue() // return 2

Interface

public class Queue {

    public Queue() {
        // do initialize if necessary
    }

    public void enqueue(int item) {
        // Write your code here
    }

    public int dequeue() {
        // Write your code here
    }
}

Solution

public class Queue {
    private ListNode head, tail;

    public Queue() {
        // do initialize if necessary
        head = tail = null;
    }

    public void enqueue(int item) {
        // Write your code here
        if (head == null) {
            head = tail = new ListNode(item);
        } else {
            tail.next = new ListNode(item);
            tail = tail.next;
        }

    }

    public int dequeue() {
        // Write your code here
        if (head == null) {
            return -1;
        } else {
            int ret = head.val;
            head = head.next;
            if (head == null) {
                tail = null;
            }
            return ret;
        }
    }
}