Remove Linked List Elements

Question

Problem Statement

Remove all elements from a linked list of integers that have value val.

Example

Given 1->2->3->3->4->5->3, val = 3, you should return the list as
1->2->4->5

題解

刪除鏈表中指定值，找到其前一個節點即可，將 next 指向下一個節點即可。

Python

  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution(object):
  8.     def removeElements(self, head, val):
  9.         """
  10.         :type head: ListNode
  11.         :type val: int
  12.         :rtype: ListNode
  13.         """
  14.         dummy = ListNode(0)
  15.         dummy.next = head
  16.         curr = dummy
  17.         while curr.next is not None:
  18.             if curr.next.val == val:
  19.                 curr.next = curr.next.next
  20.             else:
  21.                 curr = curr.next
  23.         return dummy.next

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.     /**
  11.      * @param head a ListNode
  12.      * @param val an integer
  13.      * @return a ListNode
  14.      */
  15.     public ListNode removeElements(ListNode head, int val) {
  16.         ListNode dummy = new ListNode(0);
  17.         dummy.next = head;
  18.         ListNode curr = dummy;
  19.         while (curr.next != null) {
  20.             if (curr.next.val == val) {
  21.                 curr.next = curr.next.next;
  22.             } else {
  23.                 curr = curr.next;
  24.             }
  25.         }
  27.         return dummy.next;
  28.     }
  29. }

源碼分析

while 循環中使用curr.next較爲方便，if 語句中比較時也使用curr.next.val也比較簡潔，如果使用curr會比較難處理。

複雜度分析

略