LeetCode演算法題-Remove Linked List Elements(Java實現)
這是悅樂書的第189 次更新,第191 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第48題(順位題號是203)。移除單鏈表中節點值為val的節點。例如:
輸入:1-> 2-> 6-> 3-> 4-> 5-> 6,val = 6
輸出:1-> 2-> 3-> 4-> 5
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
特殊情況:當給定的連結串列中的節點值與val全都相等時,此時需要返回空。
正常情況:因為開始時就已經將連結串列判斷了一遍,所以當進入下面的程式碼的時候,head節點的value肯定和val不相等。對此,我們在迴圈開始的時候,可以直接從head的下一個節點開始,如果head下一個節點的值和val相等,head下一個節點就需要指向其下下個節點。
public ListNode removeElements(ListNode head, int val) { while (head != null && head.val == val) { head = head.next; } if (head == null) { return head; } ListNode p = head; while (p.next != null) { if (p.next.val == val) { p.next = p.next.next; } else { p = p.next; } } return head; }
03 第二種解法
此解法和第一種解法類似,但是不同的地方是將判斷是否有相同節點值的迴圈換成了另外一種處理方式。因為核心的思路是判斷節點值是否相等,但是迴圈是從head節點的下一個節點開始的,並不是從head開始,所以我們要在head節點的前面加上一個節點,讓head節點變成第二節點,新節點變成我們需要迴圈處理的物件。在最後返回的時候,我們也是需要返回新節點的下一節點,也就是原來的head。
public ListNode removeElements2(ListNode head, int val) { ListNode res = new ListNode(0); res.next = head; ListNode pre = res; while (pre.next != null) { if (pre.next.val == val) { pre.next = pre.next.next; } else { pre = pre.next; } if(pre == null) break; } return res.next; }
04 第三種解法
上面兩種解法都是使用迭代的方法,此解法是使用遞迴的思路,先進入到連結串列的最後一位節點,然後反過來依次判斷節點值是否相等,等於就跳到下一個節點,不等於就返回當前節點,來作為head的下一個節點。
public ListNode removeElements3(ListNode head, int val) { if (head == null) { return null; } head.next = removeElements3(head.next, val); if (head.val == val) { return head.next; } else { return head; } }
05 小結
演算法專題目前已連續日更超過一個月,演算法題文章48 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!