基础知识

数据结构初始化

// 链表节点定义
public class ListNode {
// 结点的值
int val; // 下一个结点
ListNode next; // 节点的构造函数(无参)
public ListNode() {
} // 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
} // 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
} // 单链表定义
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head; //初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(-1);
}
} // 双链表定义
class ListNode{
int val;
ListNode next,prev;
ListNode() {};
ListNode(int val){
this.val = val;
}
} class MyLinkedList { //记录链表中元素的数量
int size;
//记录链表的虚拟头结点和尾结点
ListNode head,tail; public MyLinkedList() {
//初始化操作
this.size = 0;
this.head = new ListNode(-1);
this.tail = new ListNode(-2);
//这一步非常关键,否则在加入头结点的操作中会出现null.next的错误!!!
head.next=tail;
tail.prev=head;
}
}

LeetCode 203

分析1.0

删除链表节点,①考虑空表特殊情况直接返回 ②ans为新链表头节点,第一个val不满足的节点即为头节点 ③删除节点过程, 相等删除节点,不等则p指针后移

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 特殊情况
if(head == null){
return head;
}
// 构建虚拟头结点
int cnt = 1;
ListNode ans = new ListNode(-1), p = new ListNode();
p.next = head;
while(p.next != null){
if(p.next.val == val){
p.next = p.next.next;
continue;
}
if(p.next.val != val){
if(cnt == 1){
ans = p.next;
cnt = 0;
}
p = p.next;
}
}
return ans.val==-1 ? null : ans;
}
}

分析2.0

上面的分析只使用了一个p指针,而新的头结点是计算出来的,并不是统一计算而来。

改进:

设置cur、pre指针,设置虚拟头结点virtualHead

相等时删除 不等时后移

收获:① 使用多个指针简化思维难度 ②新建节点时可以直接将head作为参数传进去

ListNode virtualHead = new ListNode(-1, head);
ListNode pre = virtualHead;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return virtualHead.next;

LeetCode 707

分析1.0

乍一看有点懵,题目给出的条件有点少,光给个构造器,其他怎么啥也没有,属性呢???我链表的头结点咋办呢???要我自己定义节点吗???

我用内部类定义了Node节点,出了点问题,mark一下:

内部类 

待总结!!! 留个坑

delete报错

public void deleteAtIndex(int index) {
ListNode pre = new ListNode(-1);
ListNode p = head;
pre.next = p;
int cnt = 1;
if(index > 0 && index <= size)
while(cnt <= index){
pre = p;
p = p.next;
pre.next = p;
cnt++;
}// 考虑只有一个元素,要删除第一个元素的特殊情况 用虚拟节点
System.out.println("cnt:" + cnt);
System.out.println("p指针:" + p.val);
log();
pre.next = p.next;
p = pre.next;
this.size--;
}

分析2.0

看了解析,意识到LinkeList的属性应该设置哪些

难点 delete

public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index ; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}

LeetCode 206

分析1.0

反转链表,第一个节点和最后一个节点互换位置,第二个节点和倒数第二个节点互换位置 ...  一共n个元素 则互换 n/2 次 ,这是二分的思路

class Solution {
public ListNode reverseList(ListNode head) {
// 指定虚拟头结点
ListNode p = new ListNode(-1,head);
int num = 0;
while(p.next != null){
p.next = p.next.next;
num++;
}
// 打印信息 判断p位置
System.out.println(num);
System.out.println(p.val);
for(int i = 0; i<= num/2; i++){
}
return head;
}
}

失误 

从后往前的节点该怎么遍历呢?虽然可以用计数器确定循环终止条件,但是链表和数组不一样,不能实现随机访问

注意 ①将思路变为代码的过程极为重要,在写之前就要弄清楚关键步骤的代码如何实现

分析2.0

灵光一现,可以遍历的时候采用尾插法将节点添加到末尾 qiao

class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return head;
}
// 指定虚拟头结点
ListNode ret = new ListNode(-1);
// 遍历指针
ListNode p = head,temp;
while(p != null){
temp = p.next;
p.next = ret.next;
ret.next = p;
//System.out.println(p.val);
p = temp;
}
return ret.next;
}
}

这题没这么复杂,一开始就不要想偏,误入歧途真的很难顶

注意

① 画图分析节点的插入过程 ② 节点next指向新节点后就不是原来的那个节点了

分析3.0

我的思路被头结点局限住了,头结点是可以变化的,指针反向,新的头结点就是原来的最后一个节点 o(╥﹏╥)o

总结

  1. 题目空间复杂度要求不高就造内存
  2. 解题思路关键步骤的代码如何实现要在敲代码前明确 解题思路关键步骤的代码如何实现要在敲代码前明确 解题思路关键步骤的代码如何实现要在敲代码前明确
  3. 链表节点操作模拟要画图
  4. 自定义一个数据类型,如链表等,要考虑属性 元素个数 、构造器
  5. 链表删除 虚拟头结点next指针指向原链表 pre + p 双指针删除 特别是配合索引删除 p移动 pre也要移动
  6. 如何使用计数器实现定位

常用变量名增量更新

size、val、ans、cnt

 
 
 

最新文章

  1. IOleItemContainer的接口定义
  2. PHP简单post验证绕过
  3. [ZOJ 1005] Jugs (dfs倒水问题)
  4. uploadify 使用 详细 说明
  5. Android:源码环境编译自定义的APP到ROM(System Image)中
  6. Android Splash界面支持用户点击 直接进入主界面
  7. JAVA设计模式:模板设计模式
  8. C# ref与out
  9. Java进阶篇设计模式之十三 ---- 观察者模式和空对象模式
  10. USB鼠标键盘数据格式以及按键键值
  11. python实现ssh远程登录
  12. Windows Internals 笔记——内核对象
  13. Mariadb Redis 的配置使用
  14. [ 9.29 ]CF每日一题系列—— 765B字符串规律
  15. C# 爬虫小程序
  16. Python: 正则表达式匹配多行,实现多行匹配模式
  17. 【Cocos2d-Js实战教学(1)横版摇杆八方向移动】
  18. Linux bash脚本及常用命令--不断更新中
  19. thinkphp中的session的使用和理解!
  20. MongoDB整理笔记のSharding分片

热门文章

  1. 深入浅出Seata的AT模式
  2. 数据结构学习——BST删除特定节点
  3. Android-helloword
  4. Go适合做什么?为何这么多人偏爱Go语言?
  5. 新项目决定用 JDK 17了
  6. json提取器和beanshell处理器组合,将提取的所有id以数组返回
  7. 10、RestTemplate方式实现远程调用Client
  8. VS2019注册码
  9. 聚合查询、分组查询、ORM中如何给表再次添加新的字段、F与Q查询、ORM查询优化、ORM事务操作、ORM常用字段类型、ORM常用字段参数、Ajax、数据编码格式(Content-Type)、ajax携带文件数据
  10. day10-AOP-03