算法总结之 在单链表和双链表中删除倒数第k个节点
2024-08-28 20:34:54
分别实现两个函数，一个可以删除单链表中倒数第k个节点，另一个可以删除双链表中倒数第k个节点
思路：
如果链表为空，或者k<1 参数无效
除此之外 让链表从头开始走到尾，每移动一步，就让k的值减1
当链表走到头时候 如果k值大于0 说明不用调整 因为链表根本没有倒数第k个节点 此时将原链表直接返回即可
如果k值=0，说明链表倒数第k个节点就是头节点，此时直接返回head.next 也就是原链表的第二个节点 让第二个节点作为链表的头节点，此时直接返回head.next
如果k值<0 重新从头开始走，没移动一步 k值加1 当k值等于0时，停止 移动到的节点就是要删除节点的前一个节点
废话不多说，上代码！
package TT;
public class Test85 {
public class Node{
public int value;
public Node next;
public Node(int data){
this.value = data;
}
}
public static Node removeLastKthNode(Node head, int lastKth){
if(head==null || lastKth<1){
return head;
}
Node curNode = head;
Node cur = head;
while(cur!= null){
lastKth--;
cur=cur.next;
}
if(lastKth == 0){
head = head.next;
}
if(lastKth<0){
cur = head;
while(++lastKth !=0){
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
}
双链表的问题，几乎与单链表处理如出一辙 要注意last指针的重连即可
package TT;
public class Test86 {
public class DoubleNode{
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data){
this.value = data;
}
}
public DoubleNode removeLastKthNode(DoubleNode head, int lastKht){
if(head==null || lastKht<1){
return head;
}
DoubleNode cur = head;
while(cur!=null){
lastKht--;
cur = cur.next;
}
if(lastKht==0){
head=head.next;
head.last = null;
}
if(lastKht<0){
cur = head;
while(++lastKht !=0){
cur = cur.next;
}
DoubleNode newNext = cur.next.next;
cur.next = newNext;
if(newNext != null){
newNext.last =cur;
}
}
return head;
}
}
最新文章
- 谈谈JS中的函数节流
- MongoDB-分片片键
- NetCDF 入门
- logstash 配置文件实例
- iOS工作笔记(十四)
- 内存不足 java.lang.OutOfMemoryError: PermGen space
- Mysql 下 Insert、Update、Delete、Order By、Group By注入
- usaco 购买饲料 && 修剪草坪
- orainstRoot.sh到底执行了哪些操作
- 山东省赛A题：Rescue The Princess
- Visual C++基础知识（ｗｉｎ３２ｅｘｅ）
- poj 1001 求高精度幂
- 队列的实现 -- 数据结构与算法的javascript描述 第五章
- 实用推荐：12款Linux系统恢复工具
- 【原】谈谈promise
- 使用SigbalR发送通知
- sql查询表说明
- 初学Python（三）——字典
- Linux中dos2unix批量转换
- css 之过渡效果