删除链表的倒数第N个节点
【摘要】 实现俩个函数,一个可以删除单链表中倒数第N个节点,另一个可以删除双链表中倒数第N个节点要求:如果链表长度为L,则时间复杂度为O(L),空间复杂度为O(1)力扣对应题目:https://leetcode.cn/problems/SLwz0R/ 删除链表的倒数第n个节点双指针删除,直接3指向5,即4的前一个节点,指向4的后一个节点n1.next = n1.next.next当n = 1时候,在...
- 实现俩个函数,一个可以删除单链表中倒数第N个节点,另一个可以删除双链表中倒数第N个节点
- 要求:如果链表长度为L,则时间复杂度为O(L),空间复杂度为O(1)
力扣对应题目:https://leetcode.cn/problems/SLwz0R/ 删除链表的倒数第n个节点
双指针
删除,直接3指向5,即4的前一个节点,指向4的后一个节点
n1.next = n1.next.next
当n = 1时候,
在第一个节点之前,创建0节点,空节点
如果n值小于0,如果找到要删除节点的前一个节点呢?
- 重新从头节点开始走,每移动一步,就让N的值+1
- 当N = 0,移动停止,移动到的节点就是要删除节点的前一个节点
public Node removeLastKthNode(Node head, int lastKth){
if(head == null || lastKth < 1){
return head;
}
Node cur = head;
while(cur != null){
lastKth--;
cur = cur.next;
}
if(lastKth == 0){
head = head;
}
if(lashKth < 0){
cur = head;
while(++lastKth != 0){
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
- 时间复杂度:O(L)O(L)O(L),其中 LLL 是链表的长度。
- 空间复杂度:O(1)O(1)O(1)。
对于双链表的调整几乎和单链表的处理方式一样,注意last指针的重连,具体实现如下:
public Node removeLastKthNode(Node head, int lastKth){
if(head == null || lastKth < 1){
return head;
}
Node cur = head;
while(cur != null){
lastKth--;
cur = cur.next;
}
if(lastKth == 0){
head = head。next;
head.last = null;
}
if(lashKth < 0){
cur = head;
while(++lastKth != 0){
cur = cur.next;
}
Node newNext = cur.next.next;
cur.next = newNext;
if(newNext != null){
newNext.last = cur;
}
}
return head;
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)