问答

当前位置
  • 首页
  • 问答
  • 493.Implement Queue by Linked List II 单向链表解法

493.Implement Queue by Linked List II 单向链表解法

  • Ta: 李玉哲

我用单向链表写了这道题的答案,AC了,助教老师可以看看有没有什么问题吗?对比于用双向链表,唯一的缺点应该就是时间复杂度在pop_back和push_back的时候需要O(n),n为链表长度,而双向链表只要O(1)。push_front和pop_front则没有区别,两种链表的解法都是O(1)。对吗?

class Node {
    int val;
    Node next;
    Node(int val) {
        this.val = val;
        this.next = null;
    }
}


public class Dequeue {
    Node head;
    public Dequeue() {
        this.head = null;
    }

    /*
     * @param item: An integer
     * @return: nothing
     */
    public void push_front(int item) {
        Node node = new Node(item);
        node.next = head;
        head = node;
    }

    /*
     * @param item: An integer
     * @return: nothing
     */
    public void push_back(int item) {
        Node node = new Node(item);
        if (head == null) {
            head = node;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    /*
     * @return: An integer
     */
    public int pop_front() {
        if (head == null) {
            return -1;
        }
        if (head.next == null) {
            int val = head.val;
            head = null;
            return val;
        }
        int val = head.val;
        head = head.next;
        return val;
    }

    /*
     * @return: An integer
     */
    public int pop_back() {
        if (head == null) {
            return -1;
        }
        if (head.next == null) {
            int val = head.val;
            head = null;
            return val;
        }
        Node prev = head, cur = head.next;
        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
        prev.next = null;
        return cur.val;
    }
}

1 个回复

2019-09-09 carry

理解对的,这题你用单向队列也是可以AC的

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1