19.删除链表的倒数第N个节点 Java版本 勘誤

[Haoze0102]

原版本

public ListNode removeNthFromEnd(ListNode head, int n){
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;

    ListNode fastIndex = dummyNode;
    ListNode slowIndex = dummyNode;

    // 只要快慢指针相差 n 个结点即可
    for (int i = 0; i < n  ; i++){ 
        fastIndex = fastIndex.next;
    }

    while (fastIndex != null){
        fastIndex = fastIndex.next;
        slowIndex = slowIndex.next;
    }

    //此时 slowIndex 的位置就是待删除元素的前一个位置。
    //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
    slowIndex.next = slowIndex.next.next;
    return dummyNode.next;
}

實際應改為

public ListNode removeNthFromEnd(ListNode head, int n){
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;

    ListNode fastIndex = dummyNode;
    ListNode slowIndex = dummyNode;

    // 只要快慢指针相差 n 个结点即可
    for (int i = 0; i < n + 1  ; i++){  //改為n+1
        fastIndex = fastIndex.next;
    }

    while (fastIndex != null){
        fastIndex = fastIndex.next;
        slowIndex = slowIndex.next;
    }

    //此时 slowIndex 的位置就是待删除元素的前一个位置。
    //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
    slowIndex.next = slowIndex.next.next;
    return dummyNode.next;
}

[regancz]

我也发现了这个问题 或者修改while的条件： while (fastIndex != null && fastIndex.next != null)

[eurakalee]

我也发现这个问题，在不改动for循环的基础上，while循环也可以修改为： public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode fastNode = dummy; ListNode slowNode = dummy;

    for (int i = 0; i < n  ; i++){
        fastNode = fastNode.next;
    }
    while(fastNode.next != null){
        fastNode = fastNode.next;
        slowNode = slowNode.next;
    }
    slowNode.next = slowNode.next.next;
    return dummy.next;

}

[Aaaakkey]

改动： 改变for循环添加 i<=n 使快慢指针之间相差n+1步，使慢指针指向被删除元素的上一个 原版： i<n 使快慢指针之间相差n步，使慢指针指向被删除元素 class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dumyNode = new ListNode(-1); dumyNode.next = head; ListNode slowNode = dumyNode; ListNode fastNode = dumyNode; for( int i = 0 ; i <= n; i++){ fastNode = fastNode.next; } while(fastNode != null){ fastNode = fastNode.next; slowNode = slowNode.next; } slowNode.next = slowNode.next.next; return dumyNode.next; } }