[剑指Offer]18-题目一:删除链表的节点 题目二:删除链表中重复节点
2024-08-31 11:24:17
题目一
题目
O(1)时间复杂度删除给定链表节点。
题解
用待删除节点后一个节点的值覆盖待删除节点值,更新链接关系。
注意链表只有一个节点;删除尾结点;删除头节点的处理。
代码
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) {
//test case
ListNode n1=new ListNode(1);
ListNode n2=new ListNode(1);
ListNode n3=new ListNode(2);
ListNode n4=new ListNode(3);
//n1.next=n2;
n2.next=n3;
n3.next=n4;
ListNode pHead=deleteNode(n1,n1);
ListNode p=pHead;
while(p!=null){
System.out.println(p.val);
p=p.next;
}
}
public static ListNode deleteNode(ListNode pHead,ListNode node) {
if(pHead==null||(pHead.next==null&&node==pHead)) {//一个节点单独判断,方便后面
return null;
}
if(node.next==null) {//删除尾结点,仍要遍历整个链表
ListNode pNode=pHead;
while(pNode.next!=node) {
pNode=pNode.next;
}
pNode.next=null;
}
else {//删除其他节点
if(node==pHead) {//删除头结点,更新pHead
pHead=node.next;
}
node.val=node.next.val;
node.next=node.next.next;
}
return pHead;
}
}
题目二(再练习)
题目
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
题解
- 增加一个头结点,三个指针pL,pR,p,分别代表:pL.next()是答案的头结点,pR是尾结点,p是待处理节点。
- 在待判断节点剩两个及两个以上情况下:
- 判断p和p.next()节点值是否相同,相同找到所有连续节点,删除;不同则直接连上。
- 最后返回pL.next();
代码
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) {
//test case
ListNode n1=new ListNode(1);
ListNode n2=new ListNode(1);
ListNode n3=new ListNode(2);
ListNode n4=new ListNode(3);
n1.next=n2;
n2.next=n3;
n3.next=n4;
ListNode pHead=deleteDuplication(n1);
ListNode p=pHead;
while(p!=null){
System.out.println(p.val);
p=p.next;
}
}
public static ListNode deleteDuplication(ListNode pHead) {
if(pHead==null||pHead.next==null) {
return pHead;
}
ListNode pL=pHead.val==-1?new ListNode(-2):new ListNode(-1);//在原始链表前加一个不相同的头结点,最后返回头结点的下一个节点。
pL.next=pHead;
ListNode pR=pL;//新链表的尾结点
ListNode p=pHead;//待判断节点
while(p!=null&&p.next!=null) {
if(p.val==p.next.val) {//如果有连续相等的节点就全部去掉,此时尾结点不需要更新
int val=p.val;
while(p!=null&&p.val==val) {
p=p.next;
}
pR.next=p;//去掉连续相同节点
}else {//如果是只出现一次的节点连接上,更新链表的尾结点
pR=p;
p=p.next;
}
}
return pL.next;
}
}
最新文章
- mysql的enum和set数据类型
- Java异常处理机制 try-catch-finally 剖析
- R语言-用R眼看琅琊榜小说的正确姿势
- java Servlet(续)
- PyQt之布局&;无边框&;信号
- POJ 2001:Shortest Prefixes
- iOS开发之拖动图片
- Linux Shell入门(转载)
- tableView的基本使用(改良版)
- AXIS2远程调用WebService示例(Eclipse+AXIS)
- Gist - ES6 Proxy
- .Net中关于相等的问题
- Java集合详解5:深入理解LinkedHashMap和LRU缓存
- git冲突解决办法合集
- 潜在风险的频次vs潜在风险的严重影响的程度(以及恢复)
- MongoDB存储引擎选择
- easyui的combobox,自动搜索的下拉框
- Git 经常使用命令合集
- (转)MP4文件两种格式AVC1和H264的区别及利用FFMPEG demux为h264码流事项
- 2018.09.26 洛谷P2464 [SDOI2008]郁闷的小J(map+vector)
热门文章
- span和input布局时对不齐
- 【译】GitHub 为什么挂?官方的可行性报告为你解答
- Ubuntu 16.04 sudo免密码visudo sudoers设置
- Mybatis-06-Lombok
- excel如何复制筛选内容
- mysql无法远程连接问题(ERROR 1045 (28000): Access denied for user 'root')
- 深入源码理解Spark RDD的数据分区原理
- JavaScript学习系列博客_15_栈内存、堆内存
- 团队作业4:第六篇Scrum冲刺博客(歪瑞古德小队)
- Arduboy基本用法(一)