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

leetcode链接：
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

方案一

方法一：两次遍历扫描，第一次确定所在位置，第二次找到元素位置删除

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode start = new ListNode();

        start.next = head;

        ListNode temp = head;
        int size = -1;
        // 统计链表的长度
        while (temp != null) {
            size++;
            temp = temp.next;
        }

        size = size - n + 1;

        // 异常判断，此时n大于链表的长度,不进行删除
        if (size < 0) {
            return head;
        }

        //尝试找到需要删除节点的前一个节点
        temp = start;
        while (size > 0) {
            size--;
            temp = temp.next;
        }

        temp.next = temp.next.next;
        return start.next;
    }
}

Accepted

• 208/208 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 62.48 % of java submissions (39.5 MB)

分析

时间复杂度：
O( 2 * n ) —> O( n )

空间复杂度：
O( 1 )

方案二

将链表放入List中，然后对List进行操作。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        List<ListNode> list = new ArrayList<>();

        ListNode start = new ListNode();

        start.next = head;

        ListNode temp = start;
        int i = 0;

        while (temp != null) {
            list.add(i++, temp);
            temp = temp.next;
        }

        int local = list.size() - n - 1;
        list.get(local).next = list.get(local).next.next;

        return start.next;
    }
}

Accepted

• 208/208 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 54.89 % of java submissions (39.6 MB)

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

较优方案—双指针

妙蛙

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 方法三：
        ListNode start = new ListNode();
        start.next = head;
        ListNode left = start;
        ListNode right = start;

        for (int i = n; i >= 0; i--) {
            right = right.next;
        }

        while (right != null) {
            right = right.next;
            left = left.next;
        }

        left.next = left.next.next;

        return start.next;
    }
}

Accepted

• 208/208 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 72.76 % of java submissions (39.5 MB)