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
  6. class Solution(object):
  7. def removeElements(self, head, val):
  8. """
  9. :type head: ListNode
  10. :type val: int
  11. :rtype: ListNode
  12. """
  13. dummy = ListNode(0)
  14. dummy.next = head
  15. curr = dummy
  16. while curr.next is not None:
  17. if curr.next.val == val:
  18. curr.next = curr.next.next
  19. else:
  20. curr = curr.next
  21. 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. }
  26. return dummy.next;
  27. }
  28. }

源码分析

while 循环中使用curr.next较为方便,if 语句中比较时也使用curr.next.val也比较简洁,如果使用curr会比较难处理。

复杂度分析