题目描述

删除链表的倒数第 n 个节点。

示例：
输入：1->2->3->4->5 和 2
输出：1->2->3->5

解析

考察重点：链表的遍历和删除结点操作

定位倒数第n个结点，操作第n个结点前驱的next引用指向第n个结点后继。

实现方法：

1. 方法一：可以分两次遍历，第一遍统计整个链表的长度，计算倒数第n个结点位置；第二遍定位目标结点完成删除操作。时间复杂度O(2n)。
2. 方法二：双指针实现。第一个指针首先向前移动n-1位，然后两个指针同时移动直到第一个指针到达链表最后一个结点为止，此时第二个指针就是倒数第n个结点。时间复杂度O(n)。

实现技巧：

使用效率更高的方法二实现，但是需要做一些处理。

• 因为如果如方法二所述，第一个指针首先向前移动n-1位，两个指针遍历完之后第二个指针指向的时倒数第n个结点，这时没有办法操作起前驱的next引用，又需要遍历一次链表；
• 再者如果第一指针试图移动n位，则如果链表恰好长度小于等于n时。无法快速断定第二个指针是刚好倒数第n个元素还是链表不存在倒数第n个元素，需要额外判断。
• 定义一个头结点结点，其next引用指向链表的第一个结点。这样第一个指针移动n位，第二个指针就一定为倒数第n个结点的前一位，即倒数n-1结点；若移动小于n位，则证明链表中不存在倒数第n个结点。

代码

private class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
    if(n <= 0){
        return head;
    }
    if(null == head){
        return head;
    }
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode first = sentinel;
    ListNode second = sentinel;
    int i = 0;
    for(; i < n && first.next != null ; ++i){//first指针尝试移动n位
        first = first.next;
    }
    if(i<n){//移动距离小于n，说明链表中不存在倒数第n个结点
        return head;
    }
    //移动距离等于n，证明存在倒数第n个节点。两个指针一起移动直到第一个指向到达最后一个结点
    while(first.next != null){
        second = second.next;
        first = first.next;
    } 
    //记录要删除的结点
    ListNode delNode = second.next;
    //修改指针删除结点
    second.next = delNode.next;
    delNode.next = null;//删除结点的next置null，帮助GC回收删除结点
    //因为head结点可能会被删除，所以不可以直接返回head，要返回sentinel.next
    head = sentinel.next;
    sentinel.next = null;//帮助GC回收sentinel结点
    return head;
}

实现方法2：

可以不定义作为哨兵的头结点，我们直接移动第一个指针n次。这里分成3种情况思考：

1. 如果节点数少于n，那么移动的次数小于n。
2. 如果节点数等于n，移动的次数刚好是n，并且第一个指针指向null，不动的指针指向的就是倒数第n个节点。
3. 如果节点数大于n，移动n次后，第一个指针指向一个存在的节点，而不动的指针指向的是倒数第n+1个节点。

代码也按照这个逻辑进行编写

代码2

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(n <= 0){
        return head;
    }
    if(null == head){
        return head;
    }
    int i = 0;
    ListNode tail = head;
    while(tail != null && i < n){
        tail = tail.next;
        i++;
    }
    //节点数量小于n
    if(i < n){
        return head;
    } 
    //节点数量等于n
    if(tail == null){
        head = head.next;
        return head;
    }
    //节点数量大于n
    ListNode newHead = head;
    while(tail.next != null){
        head = head.next;
        tail = tail.next;
    }
    head.next = head.next.next;
    return newHead;
}

LeetCode上执行结果

LeetCode上代码2执行结果