• 博客内容:LeetCode 训练营

  • 作  者:陈大大陈

  • 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信!

  • 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有问题请私信

移除链表元素

203. 移除链表元素

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

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7输出:[]

提示:

列表中的节点数目在范围[0, 104]

1 <= Node.val <= 50

0 <= val <= 50

思路

  • 题目思路:要移除值为val的元素,就涉及到了单链表的头删和中间位置删除,这就需要我们定义一个prev指针指向要删除元素的前一个元素,然后让它指向要删除元素的后一个元素。
  • prev指针一开始定义为NULL,当链表当前位置即为要删除元素的位置且prev指针为空时,就需要用到单链表头删的知识来考虑这一种情况。
  • 不需要删除的情况就让prev指针指向tail指针的位置,让tail指向下一个位置。
  • 需要删除且不为头删时,写法就是单链表中间删除的写法,让前一个指针指向删除位置的下一个,把要删除的位置free掉即可。

源码

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*tail=head,*prev=NULL;while(tail!=NULL){if(tail->val!=val){prev=tail;tail=tail->next;}else{if(prev==NULL){head=head->next;tail=head;}else{prev->next=tail->next;free(tail);tail=prev->next;}}}return head;}

反转链表

206. 反转链表

给你单链表的头节点head,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]输出:[2,1]

示例 3:

输入:head = []输出:[]

提示:

  • 链表中节点的数目范围是[0, 5000]
  • -5000 <= Node.val <= 5000

思路

反转单链表,我采用头插法,对每一个结点采用头插。

定义一个中间变量temp,将cur->next赋值给它,保存它的值,便于一会使用。

定义一个pre为空,让cur->next指向它。一开始的情况是这样的。

之后我们将cur的值赋给pre,让cur指向它的下一个。

可它的next已经变成pre了,没法直接cur=cur->next。

这是我们上面定义的temp就派上用场了。

将temp的值赋给cur。

这时的情况变成了这样。

这样到最后,情况会变成这样。

所以循环的条件应该是while(cur)。

源码

struct ListNode* reverseList(struct ListNode* head){struct ListNode*cur=head,*pre=NULL;while(cur){struct ListNode*temp=cur->next;cur->next=pre;pre=cur;cur=temp;}return pre;}

如果大家有更好的方法,请一定要私信教教我!求大佬带带。