19.Remove Nth Node From End of List (E)

1.Description(Easy)

Given a linked list, remove the nthnode from the end of list and return its head.

Notice

The minimum number of nodes in list is n.

Example

Given linked list:1->2->3->4->5->null, andn=2.

After removing the second node from the end, the linked list becomes1->2->3->5->null.

2.Code

Version 1:

设置dummy,让slow等于dummy

fast先走N步，再让fast,slow一起走，这样fast走到最后时，slow在倒数n+1上，

直接slow.next=slow.next.next移除就好了

注意中间移动fast时如果发现fast为null就直接返回null

ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null || n<=0){
            return null;
        }


        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode fast=head;
        ListNode slow=dummy;

        for(int i=0;i<n;i++){
            if(fast==null){
                return null;
            }
            fast=fast.next;
        }

        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        slow.next=slow.next.next;
        return dummy.next;
    }

Version 2:

我们直接看解法代码：

// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
    
private ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k 个节点
    return p2;
}

这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，可以用我们实现的 findFromEnd 来操作。

不过注意我们又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。

但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。