删除链表的倒数第N个节点 Posted on 2021-07-13 00:00:00 2021-07-13 00:00:00 by Author 摘要 给定一个单链表，你能遍历一趟找到链表的倒数第n个节点吗？？？？ # 删除链表的倒数第N个节点 > 写于2021/05/23 1. 题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。(尝试使用一趟扫描实现)。 **提示：** - 链表中结点的数目为 `sz` - `1 <= sz <= 30` - `0 <= Node.val <= 100` - `1 <= n <= sz` 2. 示例描述： - 示例一： - 输入：head = [1,2,3,4,5,6], n = 2 - 输出：[1,2,3,4,6] - 示例二： - 输入：head = [1,2], n =2 - 输出：[2] 3. 解题思路：该题难点如下：要删除单链表的倒数第n个节点，由于是单链表，而且是删除倒数的结点，这就增加了解题的难度，同时还需要扫描一遍来解决这个问题。这就更难。 对于这题首先解决找到倒数第n个节点的前驱节点的位置，这样就能方便删除了，要怎么找尼，我举一个简单的例子，首先我们找到一个长度为n的木棍，这个木棍长度不变，然后这个木棍的头端从所给的链表表头移动，当木棍的尾部移动到链表的尾部，那么木棍头部所在的位置就是该链表的倒数第N个节点，这样我们就能解决找到链表倒数第n个节点，然后删除该节点，同时也是扫描一趟来解决该问题的，符合题目要求，最后返回链表的表头即可，详细实现如下。 4. 代码实现： ```java public ListNode removeNthFromEnd(ListNode head, int n) { //定义木棍的头部节点，尾部节点，与指向木棍头部节点的前驱节点 ListNode pointStart = head, pointEnd = head, pointPre = head; //定义一个这个节点主要目的是删除倒数第n个节点，这个节点刚好是头节点，那么增加一个指向头节点的节点，方便删除 ListNode preHead = new ListNode(); preHead.next = head; //木棍初始值为1 int k = 1; //找到长度为n的木棍，即就是找到木棍的头部和尾部所指向的位置 while (pointEnd.next != null) { pointEnd = pointEnd.next; k++; //如果木棍长度已经为n，那么头节点也相继移动，同时指向木棍头节点的前驱节点也要移动 if (k > n) { pointPre = pointStart; pointStart = pointPre.next; } } //如果木棍的头部没有移动，说明要删除链表的头节点 if (pointStart == head) { preHead.next = pointStart.next; } //否则删除长度为n的木棍的头节点 else { pointPre.next = pointStart.next; } //最后返回链表的头节点即可 return preHead.next; } ```
{{ item.content }}
{{ child.content }}