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

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

难度中等

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

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

img

输入：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

19. Remove Nth Node From End of List

Medium

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

Example 1:

img

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解题思路

标签：链表
整体思路是让前面的指针先移动n步，之后前后指针共同移动直到前面的指针到尾部为止
cur 先向前移动n步
之后 pre 和 cur 共同向前移动，此时二者的距离为 n，当 cur 到尾部时， pre 的位置恰好为倒数第 n 个节点的前一个节点
因为要删除该节点，所以要移动到该节点的前一个才能删除，所以循环结束条件为 cur.next != null
为什么不直接返回 head 呢，因为 head 有可能是被删掉的点
时间复杂度：O(n)

image-20210427094833883

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            n--;
            if (n == -1) {
                pre = head;
            }
            if (n < -1) {
                pre = pre.next;
            }
            cur = cur.next;
        }
        if (n > 0) {
            return head;
        }
        if (pre == null) {//n==0 pre==null,说明删除的是head
            return head.next;
        }
        //n<=-1
        pre.next = pre.next.next;//找到删除的前一个节点pre，删除node
        return head;
    }
}

image-20210427095011729