Remove Linked List Elements

r囧r小猫 2022-06-09 00:58 184阅读 0赞

LeetCode 203

Difficulty: Easy

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

第一版代码

class Solution \{  
public:  
ListNode\* removeElements(ListNode\* head, int val) \{  
ListNode \*pre = new ListNode(0);  
pre->next = head;  
ListNode \*cur = head;  
while(cur)  
\{  
if (cur->val == val)  
\{  
pre->next = cur->next;  
delete cur;  
cur = pre->next;  
continue;  
\}  
pre = cur;  
cur = cur->next;  
\}  
return head;  
\}  
\};

#### Run Code Status: Fail ####

第一版代码在C艹上运行正确但在leetcode上无法通过，很气

参考discuss上一哥们的Java实现代码，思路与我的实现思路一致，他是这样实现的：

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;  
\}  
\}

发现区别在于返回的结点上，我直接返回的head，他返回的是fakehead->next。

第二版代码如下：

class Solution \{  
public:  
ListNode\* removeElements(ListNode\* head, int val) \{  
ListNode \*fakehead = new ListNode(0);  
fakehead->next = head;  
ListNode \*pre = fakehead;  
ListNode \*cur = head;  
while(cur)  
\{  
if (cur->val == val)  
\{  
pre->next = cur->next;  
delete cur;  
cur = pre->next;  
continue;  
\}  
pre = cur;  
cur = cur->next;  
\}  
return fakehead->next;  
\}  
\};

问题可能在于如果input是\[1, 2\]删除1的话，我删除后head结点已经被回收，自然无法返回，而fakehead->next结点始终存在，如果头结点存在则为头结点，不存在也有返回值，健壮性更好。