java - 设计链表 - Leetcode #707 - 得到错误的输出

Question

我正在尝试解决 LeetCode 问题 707. Design Linked List :

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the index^th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.

Example 1:

Input

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]

Output

[null, null, null, null, 2, null, 3]

Explanation

MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

想知道我的 LinkedList 出了什么问题。

无法通过输入:

["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]

[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]

我的输出为:

[null,null,null,null,null,null,null,null,6,null,null,null]

预期输出为:

[null,null,null,null,null,null,null,null,4,null,null,null]

这是我的实现:

class DoublyListNode {   
    int val;
    DoublyListNode next;
    DoublyListNode prev;

    public DoublyListNode(int val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    } 
}

class MyLinkedList {    

    DoublyListNode head;
    DoublyListNode tail;
    
    public MyLinkedList() {
       head = new DoublyListNode(-1);
       tail = new DoublyListNode(-1);

       head.next = tail;
       tail.prev = head;
    }
    
    public int get(int index) {
        DoublyListNode curr = head;
        int i = 0;

        while(tail != null && index > 0){
            curr = curr.next;
            index--;     
        }

        if(index == 0 && curr != null){
            return curr.val;
        } 
        return -1;
    }
    
    public void addAtHead(int val) {
        DoublyListNode newHead = new DoublyListNode(val);
        head.next.prev = newHead;
        head.next = newHead;
        newHead.next = head.next;
        newHead.prev = head;
    }
    
    public void addAtTail(int val) {
        DoublyListNode newTail = new DoublyListNode(val);

        tail.prev.next = newTail;
        tail.prev = newTail;
        newTail.next = tail;
        newTail.prev = tail.prev;
    }
    
    public void addAtIndex(int index, int val) {
        DoublyListNode curr = head;

        while(tail != null && index > 0){
            curr = curr.next;
            index--;
        }

        if(index == 0 && curr != null){
            DoublyListNode newNode = new DoublyListNode(val);
            newNode.prev = curr.prev;
            newNode.next = curr.next;
            curr.prev.next = newNode;
            curr.next.prev = newNode;
        }
    }
    
    public void deleteAtIndex(int index) {            
        DoublyListNode curr = head;

        while(tail != null && index > 0){
            curr = curr.next;
            index--;
        }
        if(index == 0 && curr != null && curr.next != null && curr.prev != null){
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
        }
    }
}    

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

Answer 1

您已选择实现一个双向链表，其中包含两个虚拟(哨兵)节点:head 和 tail。

这很好，但是您的代码中有几个问题:

• 在 get、addAtIndex 和 deleteAtIndex 中，从 curr 等于 开始head，这意味着如果给定索引为 0，curr 仍将是该 head，而索引 0 处的节点确实是后继节点你的头。 head 不算作节点，因为它是一个虚拟节点。因此，您应该从 curr = head.next 而不是 curr = head 开始。因此，在 deleteAtIndex 中，您不需要 if 条件的最后一部分 (curr.prev != null)，如下所示现在这是有保证的。

• 在同样的三个函数中，您有一个循环条件，表示 tail != null，但此条件始终为 true。 tail 在构造函数中初始化后永远不会被分配任何其他内容(也不应该)。循环条件应改为测试 curr != null。

• 在 addAtHead 中，您错误地连接了节点。赋值 head.next = newHead; 应该发生在newHead.next = head.next;之后，因为正如你现在所拥有的那样，你可以newHead.next 变得等于 newHead，在列表中引入一个循环。

• 在addAtTail中，赋值的顺序也是错误的。您使 newTail.prev 等于 newTail，引入一个循环。

• 在addAtIndex中有两个错误的赋值。前两个将尝试从列表中排除 curr，但它应该成为新节点的邻居。因此，您应该执行 newNode.next = curr; 而不是 newNode.next = curr.next;。 curr.next.prev = newNode; 也是错误的，因为不应更新此链接。它甚至可能导致异常，因为 curr 可能等于尾节点，而尾节点的 next 字段为 null。相反，你应该这样做 curr.prev = newNode;

没问题，但在 get 中您声明了一个未使用的变量 i。你可以放弃它。

这是应用了上述更正的代码(请参阅代码中的注释):

class DoublyListNode {
    int val;
    DoublyListNode next;
    DoublyListNode prev;

    public DoublyListNode(int val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    } 
}

class MyLinkedList {    
    DoublyListNode head;
    DoublyListNode tail;
    
    public MyLinkedList() {
        head = new DoublyListNode(-1);
        tail = new DoublyListNode(-1);

        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        DoublyListNode curr = head.next; // This is the node at index 0
        
        while (curr != null && index > 0) { // Corrected loop condition
            curr = curr.next;
            index--;
        }

        if (index == 0 && curr != null) {
            return curr.val;
        }
        return -1;
    }
    
    public void addAtHead(int val) {
        DoublyListNode newHead = new DoublyListNode(val);
        // Fixed the order of the assignments: 
        newHead.next = head.next;
        newHead.prev = head;
        head.next.prev = newHead;
        head.next = newHead;
    }
    
    public void addAtTail(int val) {
        DoublyListNode newTail = new DoublyListNode(val);
        // Fixed the order of the assignments: 
        newTail.next = tail;
        newTail.prev = tail.prev;
        tail.prev.next = newTail;
        tail.prev = newTail;
    }
    
    public void addAtIndex(int index, int val) {
        DoublyListNode curr = head.next; // This is the node at index 0

        while (curr != null && index > 0){ // Corrected loop condition
            curr = curr.next;
            index--;
        }

        if (index == 0 && curr != null) {
            DoublyListNode newNode = new DoublyListNode(val);
            newNode.prev = curr.prev;
            newNode.next = curr; // Corrected assignment
            curr.prev.next = newNode;
            curr.prev = newNode; // Corrected assignment
        }
    }
    
    public void deleteAtIndex(int index) {            
        DoublyListNode curr = head.next; // This is the node at index 0

        while (curr != null && index > 0) { // Corrected loop condition
            curr = curr.next;
            index--;
        }
        if (index == 0 && curr != null && curr.next != null) { // Removed obsolete condition
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
        }
    }
}    

下一步，您可以尝试删除一些代码重复，因为其中三个方法基本上具有相同的循环。