移除鏈表元素
- 問題
- 思路
- 代碼
- 迭代
- 遞回
問題
一個單鏈表（無傀儡節點/頭結點），洗掉指定的所有元素，
如 ：1->3->5->7->5->9 洗掉5之后；變為：1->3->7->9
思路
可以用遞回，但是空間復雜度高，
所以使用迭代，遍歷一次鏈表便洗掉所有指定節點，
使用兩個兩個指標 cur 和 prve ，
基本洗掉思路如圖片所示，
還要考慮一些細節，沒有判斷頭結點是否洗掉，所有寫到代碼注釋里面了，
代碼
如果代碼沒懂，多畫圖理解一下就會明白，
迭代
public ListNode removeElements(ListNode head, int val) {
//鏈表頭節點為空直接回傳空
if(head==null){
return null;
}
//創建兩個指標
ListNode cur=head.next;
ListNode prve=head;
//寫進回圈里，挑出條件為cur為null時，
while(cur!=null){
//判斷是否洗掉
if(cur.val==val){
prve.next=cur.next;
cur=cur.next;
}else{
prve=prve.next;
cur=cur.next;
}
}
//注意這里，用來判斷頭結點是否要洗掉的，很多人容易忘掉！！！
if(head.val==val){
head=head.next;
}
return head;
}
如果只是洗掉第一次出現的元素，只需要把回圈去掉微改一下就可以，
遞回
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
//這里就是關鍵，需要畫圖理解，
head.next = removeElements(head.next, val);
// if(head.val==val){
// return head.next;
// }else{
// return head;
// }
//簡便寫法
return head.val == val ? head.next : head;
}
遞回代碼很簡潔，但是（較抽象）需要理解，但是如果鏈表很長，那么不建議使用，防止StackOverflowError(堆疊溢位問題)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294206.html
標籤：其他