链表OJ 1移除链表元素val

来源:https://leetcode.cn/problems/remove-linked-list-elements/description/

题目:

方法一:定义prev和cur指针(双指针)

分析:

        使用两个指针prev和cur来遍历链表。prev指针指向当前节点的前一个节点，而cur指针指向当前节点。

在 while 循环中，首先检查当前节点的值是否等于val。如果相等，则需要移除该节点。

如果当前节点的值不等于val，则将prev更新为cur, cur 更新为下一个节点，以继续遍历链表。

思路一：prev不为NULL

• 如果 prev 不为 NULL，表示当前节点不是头节点，则将 prev->next 指向当前节点的下一个节点，然后释放当前节点 cur 的内存，并更新cur为 prev->next ，即下一个要检查的节点。

思路二: prev 为 NULL

• 如果 prev 为 NULL，表示当前节点是头节点，则将 cur 更新为头节点的下一个节点，释放头节点 head 的内存，并更新 head 为新的头节点 cur。

最后，返回更新后的链表头指针 head

该代码的目的是移除链表中所有值为 val 的节点，同时释放相应的内存。

代码实现: 

1.  
   struct ListNode* removeElements(struct ListNode* head, int val)
2.  
   {
3.  
   struct ListNode* prev = NULL, * cur = head;
4.  
   while (cur)
5.  
   {
6.  
   if (cur->val == val)
7.  
   {
8.  
   if (prev)
9.  
   {
10.  
    prev->next = cur->next;
11.  
    free(cur);
12.  
    cur = prev->next;
13.  
    }
14.  
    else
15.  
    {
16.  
    cur = head->next;
17.  
    free(head);//会把指针域next给free掉，因为它也是结构体的成员
18.  
    head = cur;
19.  
    }
20.  
    }
21.  
    else
22.  
    {
23.  
    prev = cur;
24.  
    cur = cur->next;
25.  
    }
26.  
    }
27.  
    return head;
28.  
    }

执行:

方法二:链表尾插

大致思路:

移除链表中所有值为val的节点，并使用尾插法构建一个新的链表，返回新链表的头指针。原始链表中不满足条件的节点会被保留，而满足条件的节点会被移除并释放内存。

尾插的思路:

函数使用三个指针cur、newhead 和 tail 来遍历和构建新的链表。

在 while 循环中，首先检查当前节点的值是否等于 val 。如果不等于 val ，则执行尾插操作将该节点添加到新链表中。

顺序:

1. 如果 tail 为 NULL，表示当前节点是新链表的第一个节点。将newhead和 tail 都指向当前节点cur
2. 接着，将 cur 更新为下一个节点，并将 tail->next 设置为 NULL，确保新链表断开
3. 此时 tail 不为 NULL，表示当前节点需要添加到新链表的尾部。将 tail->next 指向当前节点 cur ，然后更新 tail 为 tail->next,新链表链接起来实现尾插。
4. 接着持续2的操作

如果当前节点的值等于 val ，则需要移除该节点。将 cur 更新为下一个节点，并释放当前节点 del 的内存。

最后，返回新链表的头指针 newhead

画图:

代码实现:

1.  
   //尾插
2.  
   struct ListNode* removeElements(struct ListNode* head,int val)
3.  
   {
4.  
   struct ListNode*cur=head;
5.  
   struct ListNode *newhead=NULL,*tail=NULL;
6.  
   while(cur)
7.  
   {
8.  
   if(cur->val!=val)
9.  
   {
10.  
    if(tail==NULL)
11.  
    {
12.  
    newhead=tail=cur;
13.  
    }
14.  
    else
15.  
    {
16.  
    tail->next=cur;
17.  
    tail=tail->next;
18.  
    }
19.  
    cur=cur->next;// 这两条语句不可以调换顺序，否则tail->next=null
20.  
    tail->next=NULL;//cur=cur->next，这样写的话会尾插失败
21.  
    }
22.  
    else
23.  
    {
24.  
    struct ListNode*del=cur;
25.  
    cur=cur->next;
26.  
    free(del);//会把指针域next给free掉，因为它也是结构体的成员
27.  
    }
28.  
    }
29.  
    return newhead;
30.  
    }

代码执行:

         好了博客就分享到这里了，感谢你的来访！

这篇好文章是转载于：学新通技术网