首页 > 代码库 > 203. Remove Linked List Elements

203. Remove Linked List Elements

2024-10-07 21:58:39   214人阅读

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

Solution 1: add a sentinel to make the two conditions removing at the beginning and removing in the middle to be one condition. 

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* removeElements(ListNode* head, int val) {
12         ListNode* sentinel=new ListNode(-1);
13         ListNode* pre=sentinel, *cur=head;
14         sentinel->next=head;
15         while(cur){
16             if (cur->val==val){
17                 pre->next=cur->next;
18                 cur=pre->next;
19             }
20             else {
21                 cur=cur->next;
22                 pre=pre->next;
23             }
24         }
25         return sentinel->next;
26     }
27 };

Solution 2: only use one pointer. line 10 free the memory of the deleted node to avoid the memory leak.

 1 class Solution {
 2 public:
 3     ListNode* removeElements(ListNode* head, int val) {
 4         ListNode* sentinel=new ListNode(-1), *pre=sentinel;
 5         sentinel->next=head;
 6         while(pre->next){
 7             if (pre->next->val==val){
 8                 ListNode* delptr=pre->next;
 9                 pre->next=pre->next->next;
10                 delete delptr;
11             }
12             else pre=pre->next;
13         }
14         return sentinel->next;
15     }
16 };

 

203. Remove Linked List Elements


联系
我们