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

发表于

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战

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

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

示例 1：

1
2
ini复制代码输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]

示例 2：

1
2
ini复制代码输入： head = [1], n = 1
输出： []

示例 3：

1
2
ini复制代码输入： head = [1,2], n = 1
输出： [1]

解题：首先要遍历链表，获取链表的长度，然后再根据链表长度和n找到要删除的节点上一个节点位置，就是要定位倒数n+1个节点位置，对于倒数n+1位置来说要删除的是倒数n位置的节点，那么只要把倒数n+1位置的下一个节点指向倒数n-1位置的节点，修改一下这个指针指向就可以完成删除倒数n位置的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js复制代码 public ListNode removeNthFromEnd(ListNode head, int n) {
        // 获取链表长度
        int length = 0;
        ListNode lenNode = new ListNode(0, head);
        while (lenNode.next != null) {
            length++;
            lenNode = lenNode.next;
        }
        // 这是要删第一个节点的节奏啊
        if (length - n - 1 == -1) {
            return head.next;
        }
        ListNode copyNode = head;
        // 从头到尾一直找到要删除的节点 的上一个节点
        for (int i = 0; i < length - n - 1; i++) {
            copyNode = copyNode.next;
        }
        // 删除那个节点 改变next指向
        copyNode.next = copyNode.next.next;
        return head;
    }

或者不获取链表长度，使用两个链表来遍历，需要删除倒数第n个位置，遍历两个链表时，使得这两个链表的当前位置相差为n，当一个链表遍历到最后时，另外一个链表的位置就是倒数第n个位置。先复制一个链表2，遍历原链表节点，直到遍历n位置，然后现在同时遍历原链表和链表2，直到原链表结束（没有下一个节点），此时链表2刚好走到倒数第n个节点，因为链表2头部加了个哑节点，所以链表2的当前位置就是倒数第n节点的前一个节点，再将链表2的当前下一个节点指向下下个节点，就删除了倒数第n个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ini复制代码 public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode listNode = new ListNode(0, head);
        ListNode copyNode = listNode;
        // 先走一个 走到n位置为止
        for (int i = 0; i < n; i++) {
            head = head.next;
        }
        // 然后再一起走，直到先走的走到头为止
        // 这个时候后走的就走了链表长度-n的位置，因为后走的链表多个节点，所以刚好是要删除节点的前一个节点
        while (head != null) {
            head = head.next;
            copyNode = copyNode.next;
        }
        // 删除节点
        copyNode.next = copyNode.next.next;

        return listNode.next;
    }

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%