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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

解题思路1:遍历获取链表长度L,(L - N)即为需删除节点的前驱节点,将这个节点指向需删除节点的后驱节点。

时间复杂度为 O(L),空间复杂度为 O(1)

/**
 * 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;
        int length = 0;
        ListNode del = head;
        while (del != null) {
            length++;
            del = del.next;
        }
        length = length - n;
        del = dummy;
        while (length > 0) {
            length--;
            del = del.next;
        }
        del.next = del.next.next;
        return dummy.next;
    }
}

解题思路2:双指针遍历,快慢指针,快指针先走 n 步,然后双指针同时出发,当快指针指向 null 时,慢指针恰好到需删除指针的前驱节点。

时间复杂度为 O(L),空间复杂度为 O(1)

/**
 * 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(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        while (n != 0) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Tips:dummy node 翻译为哑节点或哨兵节点,用于避免一些边界情况,例如空链表和只有一个节点的单链表需要增加或删除。