19. 删除链表的倒数第 N 个节点

本题来自 LeetCode：19. 删除链表的倒数第 N 个节点^[1]

题目详情

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

给定一个链表: 1-2-3-4-5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1-2-3-5.

说明：给定的 n保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？

题目分析

本题可以先扫描一遍链表，记录链表的长度`length`；然后第二遍，就可以扫描到`length-n`位置，然后将后一位置`length - n + 1`节点删掉即可；但是这种解法需要扫描两趟链表，不符合进阶要求。

可以使用双指针（快慢指针），快指针先走`n`步，然后同时走；

使用一个空节点做为头节点，可以不用考虑特殊情况，比如 n 等于链表长度（即删除头节点）；

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0; i  n; i++) {
            fast = fast.next;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummy.next;
    }
}

复杂度分析：
时间复杂度： O(n)；
空间复杂度： O(1)；

参考资料

19. 删除链表的倒数第N个节点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

原文始发于微信公众号（xiaogan的技术博客）：