-
2020-04-18 00:56:03
一、思路:
遍历一遍存储节点到vector数组中,然后利用数组指向倒数第n个,将倒数n-1的节点的next指向倒数n的next
二、代码:
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { vector<ListNode*>nodeLists; ListNode *nowNode = head; while (nowNode != NULL) { nodeLists.push_back(nowNode); nowNode = nowNode->next; } int index = nodeLists.size() - n; if (index <= 0) return head->next; nodeLists[index - 1]->next = nodeLists[index]->next; delete nodeLists[index]; return head; } };
更多相关内容 -
python【力扣LeetCode算法题库】19-删除链表的倒数第N个节点
2021-01-21 16:42:33给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 进阶: 你能... -
LeetCode 删除链表的倒数第 N 个节点
2020-12-22 11:37:26给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 进阶: 你能... -
java实现删除链表倒数第n个结点
2021-03-23 20:41:29实现删除链表倒数第n个结点,并且返回头结点。示例:给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后,链表变为 1->2->3->5.说明:给定的 n 保证是有效的。思路:使用两个...实现删除链表倒数第n个结点,并且返回头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:给定的 n 保证是有效的。
思路:使用两个结点,一个是p,一个是q。先让p向前走n步,然后p和q同时向前走,当p走到头的时候,q即是倒数n+1个结点了。另q.next=q.next.next,则删除了倒数第n个结点。
有两种特殊情况:
1.链表长度小于n,则返回原链表
2.链表长度为n,则返回head.next
代码实现:
/**
* Definition for singly-linked list.--单链表的定义
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
int i;
for(i = 0; i < n; i++) //用于判断链表长度,同时让p先走n步
{
p = p.next;
if(p == null)
break;
}
if(i == n - 1 && p ==null) //链表长度为n时,头结点就是倒数第n个结点,删除头结点即可
return head.next;
if(i < n - 1 && p == null) //如果链表长度小于n,则不需要删除结点,返回原链表即可
return head;
ListNode q = head;
while(p.next != null)
{
//这时让p和q同时向前走,直到链表遍历完成
p = p.next;
q = q.next;
}
q.next = q.next.next;
return head;
}
}
-
python实现获取单向链表倒数第k个结点的值示例
2020-09-18 13:19:36主要介绍了python实现获取单向链表倒数第k个结点的值,结合实例形式分析了Python针对单向链表的定义、遍历、传值、判断等相关操作技巧,需要的朋友可以参考下 -
哨兵节点:删除链表倒数第N个节点
2020-09-03 20:56:41哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。 比如原链表为a->b->c,则加了哨兵节点的链表即为x->a->b>c,如下图: 那...01、哨兵节点
在链表的题目中,十道有九道会用到哨兵节点,所以我们先讲一下什么是哨兵节点。
哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。
比如原链表为a->b->c,则加了哨兵节点的链表即为x->a->b>c,如下图:
那我们为什么需要引入哨兵节点呢?举个例子,比如我们要删除某链表的第一个元素,常见的删除链表的操作是找到要删元素的前一个元素,假如我们记为 pre。我们通过:
pre.Next = pre.Next.Next 来进行删除链表的操作。但是此时若是删除第一个元素的话,你就很难进行了,因为按道理来讲,此时第一个元素的前一个元素就是nil(空的),如果使用pre就会报错。那如果此时你设置了哨兵节点的话,此时的pre就是哨兵节点了。这样对于链表中的任何一个元素,你要删除都可以通过pre.Next=pre.Next.Next的方式来进行,这就是哨兵节点的作用。
下面我们看一道题目,看一下哨兵节点的应用
02、题目讲解
第19题:删除链表倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例:
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
- 给定的 n 保证是有效的。
进阶:
- 你能尝试使用一趟扫描实现吗?
思路分析:
首先我们思考,让我们删除倒数第N个元素,那我们只要找到倒数第N个元素就可以了,那怎么找呢?我们**只需要设置两个指针变量,中间间隔N-1元素。当后面的指针遍历完所有元素指向nil时,前面的指针就指向了我们要删除的元素。**如下图所示:
接下来,我们只要同时定位到要删除的元素的前1个元素,通过前面讲过的删除操作,就可以很顺利的完成这道题目啦。
03、解题过程
现在我们来完整捋一遍解题过程:
- 首先我们定义好哨兵节点result,指向哨兵节点的目标元素指针cur,以及目标指针cur的前一个指针pre,此时pre指向nil。
- 接下来我们开始遍历整个链表。
- 当head移动到距离目标元素cur的距离为N-1时,同时开始移动cur。
- 当链表遍历完之后,此时head指向nil,这时的cur就是我们要找的待删除的目标元素。
- 最后我们通过pre.Next = pre.Next.Next完成删除操作,就完成了整个解题过程。
下面是解题过程图,可以看得更清楚哦。
04、题目解答
根据以上分析,我们可以得到下面的题解:
func removeNthFromEnd(head *ListNode, n int) *ListNode { result := &ListNode{} result.Next = head var pre *ListNode cur := result i := 1 for head != nil { if i >= n { pre = cur cur = cur.Next } head = head.Next i++ } pre.Next = pre.Next.Next return result.Next }
再给个java版:
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode result = new ListNode(0); result.next = head; ListNode pre = null; ListNode cur = result; int i = 1; while (head != null) { if (i >= n) { pre = cur; cur = cur.next; } head = head.next; i ++; } pre.next = pre.next.next; return result.next; } }
我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载
-
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
2022-03-08 09:04:56给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。在本题中,如果我们要删除节点 yy,我们需要知道节点 yy 的前驱节点 xx,并将 xx 的指针指向 yy 的后继节点。 但由于头节点不存在前驱节点,因此我们需要在删除头节点时进行特殊判断。 但如果我们添加了哑节点,那么头节点的前驱节点就是哑节点本身,此时我们就只需要考虑通用的情况即可。
public class DeleteNthDesc { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); //定义虚拟头头节点 int length = getLength(head); //获取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; } } class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
-
19.删除链表的倒数第N个结点
2022-01-28 21:37:56给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 -
图解:删除链表倒数第N个节点
2020-09-02 23:01:24给定一个链表,删除链表倒数第n个节点,并且返回链表的头结点。 示例: 给定一个链表:1->2->3->4->5,和 n = 2。当删除了倒数第二个节点后,链表变为 1->2->3->5。 说明: 给定的n保证是... -
(算法篇)Java实现删除链表倒数第n个节点
2022-02-24 19:21:19给你一个链表,删除链表的倒数第 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... -
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
2019-11-29 20:02:08本题是LeetCode第19题,以后题目也可能会变。...思路:用两个节点,删除让前一个节点比后一个节点先跑n次,然后两个一起跑。当前一个节点遍历结束或者为空的时候,后一个节点是要删除的元素,但是要删除... -
漫画:如何找到链表的倒数第n个结点?
2020-10-19 09:15:00————— 第二天 —————什么意思呢?我们以下面这个链表为例:给定链表的头结点,但并不知道链表的实际长度,要求我们找到链表的倒数第n个结点。假设n=3,那么要寻找的结点就是元素1... -
python 删除链表中倒数第N个节点
2021-11-23 23:58:46| 删除链表中倒数第N个节点 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:... -
删除链表的倒数第N个节点20201216
2020-12-16 09:51:36给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n ... -
建立一个带头节点的双向链表
2019-10-12 17:36:23尾插法(用尾插法建立链表);2.头插法(用头插法建立链表);3.显示(打印链表);4.求表长(输出链表长度);5.后插(在指定节点后面插入);6.前插(在指定节点前面插入);7.按位置插入(将元素插入指定位置);... -
C语言删除链表的倒数第N个节点
2021-12-08 19:06:54要求:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 解法:设置双指针,如果要删除第n个节点,就让一个指针比另外一个指针快n步 /** * ... -
删除链表的倒数第 N 个结点。给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。(GO、PHP...
2021-02-26 11:08:16给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n ... -
leetcode-java 删除链表的倒数第N个节点
2019-11-20 21:04:55删除链表的倒数第N个节点 删除链表中的节点 题目描述: 237.删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 现有一个链表 -- head = [4,5,1,9],... -
Javascript(JS)19. 删除链表的倒数第 N 个结点
2021-12-02 15:36:01Javascript(JS)实现力扣Leecode 19. 删除链表的倒数第 N 个结点 -
Leetcode(链表)删除链表的倒数第N个节点(C语言)
2021-05-23 05:03:53问题描述:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。示例:给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后,链表变为 1->2->3->5.解题思路:采用... -
给定一个链表,删除链表的倒数第n个节点并返回链表的头指针
2020-10-20 21:02:20给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 public ListNode removeNthFromEnd (ListNode head, int n) { //如果n小于等于0直接输出头结点吧 if(n<=0){ return head; } //接下来的n全都... -
Java 删除链表的倒数第N个节点
2021-01-09 21:47:19给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明:给定的 n 保证是... -
1.3.2 给定一个链表,删除链表的倒数第N个节点,并且返回链表的头结点.md
2021-11-23 14:07:001.3.2 给定一个链表,删除链表的倒数第N个节点,并且返回链表的头结点 -
python删除链表的倒数第 N 个结点
2021-01-25 22:50:31给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 LeetCode原题地址:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ 测试用例 示例 1 输入:head = [1,2,3,4,5], n = 2... -
证明:在含有n个结点的二叉链表中共有n+1个空链域
2021-05-16 22:12:42对于除了根结点以外的每个点都是有一个父亲结点,所以一共有n-1个指针指向某个结点,于是形成n-1个有内容的链域(减1即是父亲结点)所以一共有2*n-(n-1)=n+1个链域没有指向任何东西。 方法2: 二叉树中: 结点数n=n1... -
删除链表 M 个节点之后的 N 个节点(C语言)
2022-02-27 22:35:08给定链表 head 和两个整数 m 和 n. 遍历该链表并按照如下方式删除节点: - 开始时以头节点作为当前节点. - 保留以当前节点开始的前 m 个节点. ...在删除了指定结点之后, 返回修改过后的链表的头节点. -
删除链表的倒数第n个节点
2020-10-11 22:11:16删除链表的倒数第n个节点 题目描述 给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.... -
删除链表的倒数第N个节点(Java)
2019-02-13 17:54:59用一个指针来操作head节点,最好不要直接操作head节点。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class...