203.移除链表元素
题目链接：203. 移除链表元素 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
视频链接：手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili
第一想法
在链表前设置个虚拟头结点，那么删除第一个结点就和普通结点一样，最后返回虚拟头结点的next结点即可
代码随想录想法
问题
初版代码出现的问题：
虚拟头结点命名为dummyNode
用两个参数的构造器new dummyNode,即 ListNode dummyNode = new ListNode(-1,head)，既新建结点，又完成赋值。
cur = cur.next提到if-else判断逻辑外面，不管怎么样，每次cur都是要往前走的。
删除结点语句是prev.next = cur.next,画个图就明白了。
代码
/**
* 自己写的初版代码，有错误
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode virtualNode = new ListNode();//可以用两个参数的构造器合并成一句话,虚拟头结点用dummyNode
virtualNode.next=head;//先虚拟一个头结点指向head
ListNode currentNode = head;
ListNode prevNode = virtualNode;
while (currentNode != null) {
if(currentNode.val==val){
prevNode.next=currentNode.next.next;//代码逻辑有误，当删除最后一个时i，currentNode.next为空，prevNode.next指向空,.next.next就有误了。
currentNode = currentNode.next;//提到判断逻辑外面，反正都要操作
}else{
currentNode =currentNode.next;
prevNode = prevNode.next;
}
}
return virtualNode.next;
}
}
/**
* 看完代码随想录更正后的
*/
class Solution1{
public ListNode removeElements(ListNode head, int val) {
ListNode dummyNode = new ListNode(-1,head);
ListNode prev = dummyNode;
ListNode cur = head;
while (cur != null){
if(cur.val==val){
prev.next = cur.next;
}else{
prev = cur;
}
cur = cur.next;
}
return dummyNode.next;
}
}203.设计链表
题目链接/文章讲解/视频讲解：代码随想录
第一想法
熟悉链表，简单模拟就行
问题
删除时size要--，添加时size++
力扣里自定义结点是ListNode
代码
203.移除链表元素
题目链接：203. 移除链表元素 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
视频链接：手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili
第一想法
《算法通关村第二关——终于学会链表反转了》-CSDN博客
直接反转法的初始化是prev = null ,cur = head；和借助虚拟结点是不一样的。
代码随想录
写完双指针后理解递归法就比较容易一些，但是自己是写不出来的。只能感觉是理解会了，用递归法优化了两个指针一同向前移动的技巧。
代码
/**
* 建立虚拟头结点反转
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(-1,head);//新建虚拟结点
ListNode cur = head;
while (cur!=null){
ListNode next = cur.next;
cur.next = dummy;
dummy.next = cur;
cur = next;
}
return dummy.next;
}
}
/**
* 直接反转
*/
class Solution1 {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur!=null){
ListNode next = cur.next;//先拿头指针
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
/**
* 递归法
*/
class Solution2{
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
private ListNode reverse(ListNode prev,ListNode cur){
//终止条件
if(cur==null)
return prev;
ListNode next = cur.next;
cur.next =prev;
return reverse(cur,next);
}
}
