网络异常,图片无法展示
|
「这是我参与11月更文挑战的第22天,活动详情查看:2021最后一次更文挑战」
给你一个链表,删除链表的倒数第 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
进阶: 你能尝试使用一趟扫描实现吗?
本题并不难,只是在查找倒数第 n
个节点的基础上加了一个删除操作 解题思路如下:
- 根据题意可得,如果链表只有一个节点,那么此时
n
必然等于1
,那么删除倒数第一个节点之后的链表为空,所以特判如果链表只有一个节点,直接返回null
即可 - 创建虚拟头节点,因为本题删除的节点有可能是头节点,所以创建虚拟头节点可以方便我们的操作,简化处理逻辑
- 定义三个指针
pre
指向虚拟头,target
、next
指向head
- 将
next
指针向后走n
步 pre
、target
、next
一起向后走,直到next
指向null
,此时target
指向倒数第n
个节点- 将
pre
指针指向元素(也就是target
前一个元素)的next
指针指向target.next
来达到从链表中删除target
节点的目的 - 返回虚拟头节点的下一个节点即可
整体过程如下:
网络异常,图片无法展示
|
代码如下:
var removeNthFromEnd = function(head, n) { // 特判 如果链表只有一个节点,则 n 必然为1,此时删除倒数第一个节点后链表为空 if(head.next === null) return null; // 创建虚拟头节点 const vhead = new ListNode(0); vhead.next = head; // 定义三个指针 let pre = vhead, target = head, next = head; // next向后走n步 while(n){ n--; next = next.next; } // 当next不为空的时候,三个指针一起向后走 while(next){ pre = pre.next; target = target.next; next = next.next; } // 此时target指向的就是倒数第n个节点 // 通过将pre.next指向target.next的方法从链表中删除target pre.next = target.next; return vhead.next; }; 复制代码
至此我们就完成了 leetcode-19-删除链表的倒数第 N 个结点
如有任何问题或建议,欢迎留言讨论!