给定一个链表,删除链表的倒数第n?个节点,并且返回链表的头结点。
示例:
给定一个链表:1->2->3->4->5, 和n= 2.当删除了倒数第二个节点后,链表变为1->2->3->5.
说明:
给定的?n保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
看看给的东西,head是链表,n是倒数第n个节点,
先看看head是什么
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}
字典,键值对组成,key为数值,value为指针,最后一层元素的value是None,及尾节点的指针为空
如果我们正常知道节点位置,那么可以用x.val = x.next.val? x.next = x.next.next删除节点
或者直接跳过这个节点,让下一个节点指针指向下一个节点,然后返回头结点,链表给的是头结点,通过头结点找到后续节点。
然后就是如何找到这个节点了,知道是倒数第N个,给了链表,那就去找这个链表的长度。
那就遍历这个链表,从头节点开始,如果下一个节点不为空,那就是存在节点,进行计数
如果长度为1,那么计数为0,起始的head 等于None
最后i就是链表长度,然后知道长度,就知道是第几个节点,
然后要对n进行判断,如果n是1,那么就是删除唯一的节点,那么就应该返回空,输入的是列表,返回的就是列表,[ ]
然后是是去除这个节点,找到这个节点前一个节点是最简单的办法,倒数第n个,就是正数
i - n + 1
前一个就是i - n + 1 -1?
然后去寻找这个节点的前一个节点,起始为第1个节点,让他等于第二个节点,进行一次操作,for i in range(1)
所以应该是for i in range(i - n -1):然后这个节点指向下下个节点,
然后还有一种情况,n=i,那么就是删除第一个节点,那就直接返回head.next
对于链表我属实一知半解的,做两道题收获不少,继续努力。
学习的另一种办法
关键在于如何倒数,这种方法先正数N个,然后再前面添加任意个数,直到达到长度。
(具体实现不是这样的,但是这种想法)
先赋值一个链表A首先走N步,然后另开一个链表B再继续走,直到A走到头,这时B的末尾就是倒数第N个