基础知识
数据结构初始化
// 链表节点定义
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
总结
- 题目空间复杂度要求不高就造内存
解题思路关键步骤的代码如何实现要在敲代码前明确 解题思路关键步骤的代码如何实现要在敲代码前明确 解题思路关键步骤的代码如何实现要在敲代码前明确
链表节点操作模拟要画图
自定义一个数据类型，如链表等，要考虑属性 元素个数 、构造器
链表删除 虚拟头结点next指针指向原链表 pre + p 双指针删除 特别是配合索引删除 p移动 pre也要移动
如何使用计数器实现定位
常用变量名增量更新
size、val、ans、cnt
