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();//可以用兩個參數的構造器合并成一句話,虛擬頭結點用dummyNodevirtualNode.next=head;//先虛擬一個頭結點指向headListNode 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);}
}