leetcode203.移除链表元素

问题描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

题目链接：移除链表元素

示例

提示

  列表中的节点数目在范围 [0, $10^4$] 内
  1 <= Node.val <= 50
  0 <= val <= 50

具体思路

思路一

  通过查找链表中节点的值不等于val，就在新的链表上进行尾插，不过这种方式实现的时间复杂度也比较高

思路二

  通过遍历链表，查找链表中的值等于val就进行删除，将前一个节点（pre）的next指针指向它后一个节点，然后free掉当前节点（cur），然后再将当前节点的指针（cur）指向下一个节点

代码实现

//思路1
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur = head;struct ListNode* newhead=NULL;struct ListNode* tail=NULL;while(cur){if(cur->val!=val){if(tail==NULL){newhead=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;tail->next=NULL; }else{struct ListNode* del =cur;cur=cur->next;free(del);}}return newhead;
}

//思路2
/*** 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){if(prev){prev->next=cur->next;free(cur);cur =prev->next;}else{cur=head->next;free(head);head=cur;}}else{prev=cur;cur=cur->next;}}return head;
}