方法一:
使用前后两个指针,cur指向当前位置,prev指向前一个位置,通过改变指向和释放结点来删除val
初步代码,还存在问题:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
prev->next = cur->next;
free(cur);
// cur = cur->next;//错误,cur已经被释放,野指针
cur = prev->next;
}
}
return head;
}
null pointer出现了空指针
通过测试用例代码走读分析问题:
如果第一个就是要删的值,也就是头删,会出现问题
所以这种情况要单独处理
最终代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
if(prev == NULL)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prev->next = cur->next;
free(cur);
//cur = cur->next;//和下一句等价,但是cur已经释放,这句会出现野指针
cur = prev->next;
}
}
}
return head;//返回一个新的头,不需要用二级指针
}
方法二:
把不是val的值尾插到新链表
初步代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newHead= NULL,* tail = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
//尾插
if(tail == NULL)
{
newHead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
return newHead;
}
通过走读代码我们发现,当最后一个结点的值为val时,释放节点后前面尾插的结点仍然指向最后一个结点,这里只需要将tail->next置空即可,修改后代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newHead= NULL,* tail = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
//尾插
if(tail == NULL)
{
newHead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
tail->next = NULL;
return newHead;
}
但是代码仍然存在错误,运行如下:
显而易见,需要考虑链表为空的情况
改进后代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
if(head== NULL)
{
return NULL;
}
struct ListNode* newHead= NULL,* tail = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
//尾插
if(tail == NULL)
{
newHead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
tail->next = NULL;
return newHead;
}
报错:
这时代码直接指向最后一个else,此时tail为空,tail->next不合理,所以干脆前面不进行判断,而在后面对tail进行判断
最终代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newHead= NULL,* tail = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
//尾插
if(tail == NULL)
{
newHead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if(tail)
{
tail->next = NULL;
}
return newHead;
}
标签:ListNode,cur,val,next,链表,tail,Leetcode,struct
From: https://blog.51cto.com/u_15992140/6196392