LeetCode题解-19. 删除链表的倒数第N个节点

题目描述

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

思路

题意为删除倒数第n个节点，因此只需要拿到倒数第n+1个节点即可。用双指针加哑节点可以做到一次遍历。

代码

public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) {
            return head;
        }
        ListNode first = head, dummy = new ListNode(-1);
        dummy.next = head;
        ListNode second = dummy;
        // 拿到正数第n个节点
        for (int i = 0; i < n - 1; i++) {
            first = first.next;
        }
        // 拿到倒数第n+1个节点
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        // 删除第n个节点
        second.next = second.next.next;
        return dummy.next;
    }