Leetcode 19：Remove Nth Node From End of List

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

说人话：

删除链表中倒数第 N 个元素

要点：

• N 从 1 开始
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

示例：

[法1] 暴力法

思路

最简单是思路肯定是：

• 先遍历一遍链表，得到链表的长度
• 根据要删除倒数第 n 个结点得到要删除第几个结点
• 然后再遍历一遍链表，删除该结点

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
				//记录链表长度
        int size = 0;

        ListNode node = head;
        //得到链表长度
        while(node != null){
            size ++;
            node = node.next;
        }

        //得到要删除第几个结点
        int index = size - n + 1;
        
        //获取要删除结点的前一个结点
        ListNode dummyHead = new ListNode(0,head);
        ListNode pre = dummyHead;
        while(index-1 > 0){
            pre = pre.next;
            index --;
        }

        //删除要删除的结点
        pre.next = pre.next.next;
        return dummyHead.next;
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[法2] 滑动窗口

思路

本题可以利用滑动窗口的思想。定义两个指针：

• left：窗口的左边
• right：窗口的右边

left 和 right 中间夹的元素的个数就是 N。

窗口保持大小不变从左往右移动，直到 right == null 的时候，也就是遍历完链表的。因为 left 和 right 中间夹着 N 个元素，所以这个时候 left 就是我们要删除的元素。

由于题目规定了 N 一定是合法的，所以不用考虑 left 和 right 中元素个数不足 N 的情况。

由于要删除 left，所以还需要一个 pre 指针一直指向 left，方便后面删除。

由于考虑到可能会删除 head，所以再定义一个 dummyHead 虚拟头结点来消除这种差异。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        //虚拟头结点
        ListNode dummyHead = new ListNode(0,head);
        //左窗口前面的结点
        ListNode pre = dummyHead;
        //左窗口
        ListNode left = head;
        //右窗口
        ListNode right = head;
        //根据 n 建立窗口
        for(int i=0;i<n;i++){
            //由于 n 合法，所以不需要担心这里会有空指针
            right = right.next;
        }
        //滑动窗口直到  right == null
        while(right != null){
            pre = left;
            left = left.next;
            right = right.next;
        }
        //删除 left
        pre.next = left.next;
        return dummyHead.next;

    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)