LeetCode #707 设计链表实现输出错误排查求助

你的双向链表实现存在多个逻辑错误，导致链表结构混乱，最终get(4)返回错误结果。以下是具体问题和修复方案：

1. addAtHead方法：指针指向逻辑错误 #

原代码中修改指针的顺序错误，导致新节点的next指向自己：

// 错误代码
head.next.prev = newHead;
head.next = newHead;
newHead.next = head.next; // 此时head.next已经是newHead，所以newHead.next指向自己

修复：先设置新节点的next和prev，再修改原链表的指针：

public void addAtHead(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    newNode.next = head.next;
    newNode.prev = head;
    head.next.prev = newNode;
    head.next = newNode;
}

2. addAtTail方法：指针指向逻辑错误 #

类似addAtHead的问题，原代码顺序错误导致新节点的prev指向自己：

// 错误代码
tail.prev.next = newTail;
tail.prev = newTail;
newTail.prev = tail.prev; // 此时tail.prev已经是newTail，所以newTail.prev指向自己

修复：调整指针设置顺序：

public void addAtTail(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    newNode.prev = tail.prev;
    newNode.next = tail;
    tail.prev.next = newNode;
    tail.prev = newNode;
}

3. get方法：遍历起始点错误 #

原代码从哨兵head开始遍历，导致index=0返回哨兵节点的val（-1），而非第一个有效节点。同时未判断遍历后是否到达哨兵tail。
修复：从第一个有效节点head.next开始遍历，遍历过程中避免到达tail：

public int get(int index) {
    DoublyListNode curr = head.next;
    while (curr != tail && index > 0) {
        curr = curr.next;
        index--;
    }
    if (index == 0 && curr != tail) {
        return curr.val;
    }
    return -1;
}

4. addAtIndex方法：插入位置逻辑错误 #

原代码错误地将新节点插入到curr的前驱和后继之间，而非curr和curr.next之间，导致插入位置偏移。同时未处理index<0的情况。
修复：找到插入位置的前驱节点，将新节点插入到前驱和其后继之间，并处理index<0的边界情况：

public void addAtIndex(int index, int val) {
    if (index < 0) {
        addAtHead(val);
        return;
    }
    DoublyListNode curr = head;
    int count = 0;
    while (curr != tail && count < index) {
        curr = curr.next;
        count++;
    }
    if (count == index) {
        DoublyListNode newNode = new DoublyListNode(val);
        newNode.prev = curr;
        newNode.next = curr.next;
        curr.next.prev = newNode;
        curr.next = newNode;
    }
}

5. deleteAtIndex方法：遍历与删除逻辑错误 #

原代码从哨兵head开始遍历，可能错误地尝试删除哨兵节点，且未正确判断要删除的节点是否存在。
修复：从第一个有效节点开始遍历，找到目标节点后调整其前驱和后继的指针：

public void deleteAtIndex(int index) {
    DoublyListNode curr = head.next;
    int count = 0;
    while (curr != tail && count < index) {
        curr = curr.next;
        count++;
    }
    if (count == index && curr != tail) {
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;
    }
}

完整修复后的代码 #

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;
        while (curr != tail && index > 0) {
            curr = curr.next;
            index--;
        }
        if (index == 0 && curr != tail) {
            return curr.val;
        }
        return -1;
    }
    
    public void addAtHead(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        newNode.next = head.next;
        newNode.prev = head;
        head.next.prev = newNode;
        head.next = newNode;
    }
    
    public void addAtTail(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        newNode.prev = tail.prev;
        newNode.next = tail;
        tail.prev.next = newNode;
        tail.prev = newNode;
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0) {
            addAtHead(val);
            return;
        }
        DoublyListNode curr = head;
        int count = 0;
        while (curr != tail && count < index) {
            curr = curr.next;
            count++;
        }
        if (count == index) {
            DoublyListNode newNode = new DoublyListNode(val);
            newNode.prev = curr;
            newNode.next = curr.next;
            curr.next.prev = newNode;
            curr.next = newNode;
        }
    }
    
    public void deleteAtIndex(int index) {
        DoublyListNode curr = head.next;
        int count = 0;
        while (curr != tail && count < index) {
            curr = curr.next;
            count++;
        }
        if (count == index && curr != tail) {
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
        }
    }
}    

修复后，执行你的测试用例，get(4)会正确返回4，与预期输出一致。

内容的提问来源于stack exchange，提问作者Marcus Mousavi