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

Question

我正在尝试解决LeetCode问题707。设计链表:

设计链表的实现。您可以选择使用单链表或双向链表。

单链表中的节点应该有两个属性：

val

和

next

。

val

是当前节点的值，

next

是指向下一个节点的指针/引用。

如果要使用双向链表，则还需要一个属性

prev

来指示链表中的前一个节点。假设链表中的所有节点都是 0 索引。

实现

MyLinkedList

类：

• MyLinkedList()

  初始化

  MyLinkedList

  对象。

• int get(int index)

  获取链表中第

  index

  ^第节点的值。如果索引无效，则返回-1。

• void addAtHead(int val)

  在链表的第一个元素之前添加一个值为

  val

  的节点。插入后，新节点将成为链表的第一个节点。

• void addAtTail(int val)

  追加一个值为

  val

  的节点作为链表的最后一个元素。

• void addAtIndex(int index, int val)

  在链表中第

  val

  th

  节点之前添加一个值为 ^index 的节点。如果

  index

  等于链表的长度，则该节点将被追加到链表的末尾。如果

  index

  大于长度，则节点将不会被插入。

• void deleteAtIndex(int index)

  如果

  index

  有效，则删除链表中的第^index

  第

  节点。

示例1：

输入

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

输出

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

解释

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 的

  后继

  。

  head

  不算作节点，因为它是虚拟节点。所以你应该从

  curr = head.next

  而不是

  curr = head

  开始。因此，在

  deleteAtIndex

  中，您不需要

  if

  条件的最后一部分 (

  curr.prev != null

  )，因为现在可以保证这一点。

• 在相同的三个函数中，您有一个循环条件，表示

  tail != null

  ，但此条件始终为真。

  tail

  在构造函数中初始化后永远不会被分配任何其他内容（也不应该）。循环条件应改为测试

  curr != null

  。

• 在

  addAtHead

  中，您错误地连接了节点。赋值

  head.next = newHead;

  应该发生在 after

  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

   可能等于尾节点，尾节点的 

  null

   字段具有 

  next

  。相反，你应该这样做 

  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;
        }
    }
}    

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