Problem:?203. 移除鏈表元素
- 題目
- 思路
- 解題方法
- 復雜度
- Code
- 效果
題目
給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，并返回 新的頭節點 。
示例 1：
輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]
示例 2：
輸入：head = [], val = 1
輸出：[]
示例 3：
輸入：head = [7,7,7,7], val = 7
輸出：[]
提示：
列表中的節點數目在范圍 [0, 104] 內
1 <= Node.val <= 50
0 <= val <= 50
思路
單項列表節點的刪除
解題方法
設置虛擬頭節點dummy指向head
指針pre從dummy開始往后遍歷
指針cur指向當前節點（從head開始）
如果cur值等于val，則刪除cur節點
（刪除：讓pre下一個節點直接指向cur下一個節點）
復雜度
時間復雜度:
O(n)
空間復雜度:
O(1)
Code
Java
/*** 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;}ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;while(cur != null){if(cur.val == val){pre.next = cur.next;} else {pre = cur;}cur = cur.next;}return dummy.next;}
}效果
)
)
)
)
