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

描述

难度：中等

给你一个链表，删除链表的倒数第 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

假如有链表：

n=2，即删除倒数第2个节点，也就是这里的第 5-2 = 3 个节点（从0开始遍历）

假如 n=5，即要删除第一个节点，那要如何判断呢？

常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。

变成： 0—>1—>2—>3—>4—>5—>null

• 第一种解法：通过长度遍历

删除倒数第N个节点，也就是删除第 length-N 个节点。

所以第一步我们要获取这个链表的长度

我们知道要删除第3个节点 ，接下来就是找到第3个节点的前一个节点，指向当前节点的下一个节点。

第二步就是遍历这个链表，找到它的删除节点的上一个节点

• 第二种解法：辅助栈

利用 栈 找到目标删除节点，这种方法容易理解，见代码。

• 第三种解法：双指针

双指针简单一点，first 指针指向cur.next（在右），second 指向 cur（在左），如何让first 先走 n 步（n是要删除的倒数节点，假设 n=2），然后first、second 一起走到first的尾部。

1、第一步

S 在原点，F 在下一位

S  F
|  |
0—>1—>2—>3—>4—>5—>null

2、第二步

F向前走n步

S         F            
|         |            
0—>1—>2—>3—>4—>5—>null

3、第三步

判断标准为F不为空前，S、F一起走

          S             F
          |           |
0—>1—>2—>3—>4—>5—>null

S.next = S.next.next 即可

解法

public class 删除链表的倒数第N个结点19 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        listNode.next.next.next.next = new ListNode(5);

        ListNode resultListNode = removeNthFromEnd2(listNode, 5);
        printListNode(resultListNode);
    }



    /**
     *
     * 解法一，先求长度
     * 一种常用的技巧是添加一个哑节点（dummy node），它的next 指针指向链表的头节点。
     * 这样一来，我们就不需要对头节点进行特殊的判断了。
     *
     *
     * 复杂度分析
     * 时间复杂度：O(L)，其中 L 是链表的长度。
     * 空间复杂度：O(1)。
     *
     * @param head
     * @param n
     * @return
     */
    static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        //此节点前的都是正常遍历，
        //length-n+1 即删除节点前一个
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
    static int getLength(ListNode listNode) {
        int i = 0;
        while (listNode != null) {
            i++;
            listNode = listNode.next;
        }
        return i;
    }

    /**
     * 解法二：栈
     *
     * 复杂度分析
     * 时间复杂度：O(L)，其中 L 是链表的长度。
     * 空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销
     *
     */
    static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //从后往前，弹出n个栈
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        //prev是要删除的目标节点的上一个节点
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    /**
     *
     * 解法三，双指针
     *
     * 复杂度分析
     * 时间复杂度：O(L)，其中 L 是链表的长度。
     * 空间复杂度：O(1)
     *
     */
    static ListNode removeNthFromEnd4(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy.next;
        ListNode second = dummy;
        //让first先跑n步
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    /**
     * 打印链表
     *
     * @param head
     */
    static void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}