删除链表的倒数第 N 个结点

问题描述

来源：LeetCode第19题

难度：中等

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

示例 1：

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

输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1

输出：[]

示例 3：

输入：head = [1,2], n = 1

输出：[1]

提示：

• 链表中结点的数目为 sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

视频分析

代码部分

解法一

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre = head;
    // 待删除节点的位置
    int index = length(head) - n + 1;
    //如果index等于1表示删除的是头结点
    if (index == 1)
        return head.next;
    //这里首先要找到要删除链表的前一个结点
    for (int i = 1; i < index - 1; i++) {
        pre = pre.next;
    }
    //然后让前一个结点的next指向要删除节点的next
    pre.next = pre.next.next;
    return head;
}

//求链表的长度
private int length(ListNode head) {
    int len = 0;
    while (head != null) {
        len++;
        head = head.next;
    }
    return len;
}

解法二

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    //fast移n步，
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    //如果fast为空，表示删除的是头结点
    if (fast == null)
        return head.next;

    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // 因为fast和slow相差n，fast是倒数第一个节点，所以slow就是倒数第n+1个节点
    //这里最终slow不是倒数第n个节点，他是倒数第n+1个节点，
    //他的下一个结点是倒数第n个节点,所以删除的是他的下一个结点
    slow.next = slow.next.next;
    return head;
}

解法三

public ListNode removeNthFromEnd(ListNode head, int n) {
    int last = helper(head, n);
    // 说明删除的是头节点
    if (last == n)
        return head.next;
    return head;
}

// 获取节点所在位置，逆序
public int helper(ListNode node, int n) {
    if (node == null)
        return 0;
    // 当前节点是倒数第几个，因为删除的是倒数第n个节点，
    // 所以我们需要查找倒数第n+1个节点
    int last = helper(node.next, n) + 1;
    //获取要删除链表的前一个结点，就可以完成链表的删除
    if (last == n + 1)
        node.next = node.next.next;
    return last;
}