203. Remove Linked List Elements

https://leetcode.com/PRoblems/remove-linked-list-elements/?tab=Description

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

Example Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5

思路

用一个新的ListNode fakehead来处理边界情况，fakeHead.next = head;由于本题有可能删除当前节点，所以用双指针pre和curr。

代码

解法一

public class Solution { public ListNode removeElements(ListNode head, int val) { ListNode fakeHead = new ListNode(-1); fakeHead.next = head; ListNode curr = head, prev = fakeHead; while (curr != null) { if (curr.val == val) { prev.next = curr.next; } else { prev = prev.next; } curr = curr.next; } return fakeHead.next; } }

解法二 递归

个人不认为这是个好解法，如果LinkedList长度过大，会堆溢出

public ListNode removeElements(ListNode head, int val) { if (head == null) return null; head.next = removeElements(head.next, val); return head.val == val ? head.next : head; }