LeetCode题解：删除链表的倒数第N个结点

题目描述

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头节点。

示例

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

算法思路

暴力解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(0,head);
       int length = getSize(head);
       ListNode current = dummy;
       for(int i=0;i<length-n;i++){
          current = current.next;
       }
       current.next = current.next.next;
       return dummy.next;
    }

    private int getSize(ListNode head){
        int length = 0;
        while(head!=null){
            head = head.next;
            length++;
        }
        return length;
    }
}

复杂度分析

• 时间复杂度：O(L)，L是链表长度。
• 空间复杂度：O(1)。

双指针法

我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。
由于我们需要找到倒数第n个节点，因此我们可以使用两个指针first 和 second 同时对链表进行遍历，并且first 比 second 超前 nn 个节点。当first 遍历到链表的末尾时，second 就恰好处于倒数第n个节点。
具体地，初始时 first 和 second 均指向头节点。我们首先使用 \textit{first}first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了n−1 个节点，即first 比 second 超前了 nn 个节点。
在这之后，我们同时使用first 和second 对链表进行遍历。当first 遍历到链表的末尾（即first 为空指针）时，second 恰好指向倒数第n个节点。当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode first = head;
        ListNode second = dummy;
        //移动快指针到n的位置，使快指针领先慢指针n+1位
        for(int i=0;i<n;i++){
            first = first.next;
        }
        while(first!=null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(L)，L是链表长度。
• 空间复杂度：O(1)。