题目出处

19-删除链表的倒数第N个结点-题目出处

题目描述

19-删除链表的倒数第N个结点-题目描述

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

19-删除链表的倒数第N个结点-官方解法

前言

19-删除链表的倒数第N个结点-官方解法

方法1：计算链表长度

思路：

19-删除链表的倒数第N个结点-计算链表长度解法

代码示例：（Java）

public class Solution1 {
    @Data
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }


}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。

方法2:栈

思路：

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

19-删除链表的倒数第N个结点-栈解法-动图

代码示例：（Java）

public class Solution2 {
    @Data
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }


}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。

方法3:双指针

思路：

19-删除链表的倒数第N个结点-双指针解法1
19-删除链表的倒数第N个结点-双指针解法2

代码示例：（Java）

public class Solution3 {
    @Data
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }


}