題目
Remove all elements from a linked list of integers that have value val.
Example:
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
解法思路
- 首先要對(duì)傳入的頭節(jié)點(diǎn)
head做判斷，是不是不為空？是不是就是和要?jiǎng)h除的值相等？如果是的話，那么就要?jiǎng)h除頭節(jié)點(diǎn)；這個(gè)動(dòng)作一直做，直到頭節(jié)點(diǎn)不再是要?jiǎng)h除的節(jié)點(diǎn)，或者鏈表已經(jīng)被刪沒了； - 如果鏈表在上述動(dòng)作中刪沒了，那么就向外返回 null；
- 如果鏈表沒有被刪沒，那么就從頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)開始遍歷，判斷是否應(yīng)該被刪除；
- 在刪除完鏈表中所有要?jiǎng)h除的元素后，返回頭節(jié)點(diǎn)；
解法實(shí)現(xiàn)
時(shí)間復(fù)雜度
- O(N)；
空間復(fù)雜度
- O(1)；
關(guān)鍵字
鏈表 刪除鏈表中的元素
實(shí)現(xiàn)細(xì)節(jié)
- 注意對(duì)頭節(jié)點(diǎn)的判斷；
package leetcode._203;
public class Solution203_1 {
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
ListNode delNode = head;
head = delNode.next;
delNode.next = null;
}
if (head == null) {
return null;
}
ListNode prev = head;
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
} else {
prev = prev.next;
}
}
return head;
}
}
解法思路（二）
- 在鏈表的頭節(jié)點(diǎn)前鏈入一個(gè)虛擬頭節(jié)點(diǎn)，這樣就無(wú)須對(duì)頭節(jié)點(diǎn)的情況做單獨(dú)的判斷和處理；
解法實(shí)現(xiàn)（二）
時(shí)間復(fù)雜度
- O(N)；
空間復(fù)雜度
- O(1)；
關(guān)鍵字
虛擬頭節(jié)點(diǎn) 鏈表 刪除鏈表中的元素
實(shí)現(xiàn)細(xì)節(jié)
// 203. Remove Linked List Elements
// https://leetcode.com/problems/remove-linked-list-elements/description/
// 使用虛擬頭結(jié)點(diǎn)
// 時(shí)間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(1)
public class Solution2 {
public ListNode removeElements(ListNode head, int val) {
// 創(chuàng)建虛擬頭結(jié)點(diǎn)
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode cur = dummyHead;
while(cur.next != null){
if(cur.next.val == val ){
ListNode delNode = cur.next;
cur.next = delNode.next;
}
else
cur = cur.next;
}
return dummyHead.next;
}
public static void main(String[] args) {
int[] arr = {1, 2, 6, 3, 4, 5, 6};
int val = 6;
ListNode head = new ListNode(arr);
System.out.println(head);
(new Solution1()).removeElements(head, val);
System.out.println(head);
}
}
