1.反转单链表
206. 反转链表https://leetcode.cn/problems/reverse-linked-list/这里我们使用创建一个变量cur来遍历原链表，再创建一个新节点newnode，首先使用一个循环来遍历原链表，cur为NULL是循环结束，每次进入循环将cur的下一个节点赋给tail，然后将cur取下来头插，第一次头插的节点的next置为NULL，也就是cur->next=newnode,然后将cur这个节点赋给newnode，在新链表上相当于往左走一步，newnode=cur,然后cur在旧链表上往右走，cur=tail。循环结束后cur就为NULL了，也就是全部完成头插了，这是newnode也走到了新链表最左边的位置，也就是成为了头节点，这时返回newnode就行了。
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur=head;
struct ListNode* newhead=NULL;
while(cur)
{
struct ListNode* tail=cur->next;
//头插
cur->next=newhead;
newhead=cur;
cur=tail;
}
return newhead;
}
2.移除链表元素
移除链表元素https://leetcode.cn/problems/remove-linked-list-elements/首先创建一个变量newnode，用来保存新链表的头节点，再创建一个变量tail，由于新链表的尾插，再创建一个变量cur遍历原链表。
这里我们要考虑很多种情况：
1.链表为NULL，直接返回NULL。
2.如果cur->val==val,创建一个指针del保存cur，然后cur走到下一个节点，free掉del，这就是删除步骤。
3.如果cur->val!=val,进行尾插，这里也分两种情况，第一种就是新链表为空，则tail=cur=newnode。第二种就是不为空，正常尾插，先将tail->next=cur,然后tail往后走，tail=tail->next，在第三种情况里面无论走哪一步cur都要往后走一步，cur=cur->next。
循环结束之后cur就遍历完了，这时还要做的一个小细节就是判断一下tail是否为NULL，如果为NULL，就将tail->next置空即可。
返回newnode即可。
struct ListNode* removeElements(struct ListNode* head, int val)
{
if(head==NULL)
{
return NULL;
}
struct ListNode* newhead=NULL,*tail=NULL,*cur=head;
while(cur)
{
if(cur->val==val)//删除
{
struct ListNode* del=cur;
cur=cur->next;
free(del);
}
else//尾插
{
if(tail==NULL)
{
newhead=tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
}
if(tail)
tail->next=NULL;
return newhead;
}
3.求链表的中间节点
876. 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/这里就需要用到快慢指针来找中间节点，首先创建两个指针，分别为slow和fast，使用一个循环遍历链表，结束条件就是fast和fast->next其中一个为空，然后fast每次走两步，slow每次走一步，当fast走到最后一个节点，slow就是中间节点，如果链表有偶数个节点，不用担心，假设这个链表有6个节点，fast每次走两步会走到NULL这个位置，用了三次，slow走三次就走到了第四个节点，所以是刚好的。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。
相关链接
您阅读本篇文章共花了：
发表评论