一、移除链表元素
leetcode链接
题目描述:
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
思路:
正常遍历,找到value的值与题目中相同的结点去free掉,分为两种情况:
第一种就是头结点就是value值,直接将头节点指向next;
第二种情况就是第二个结点开始是value,需要有一个前结点指向value结点的下一个。
源码:
struct ListNode* removeElements(struct ListNode* head, int val)
{
//链表本身为空
if(head==NULL)
return NULL;
struct ListNode* prev = NULL;
while(1)//头节点开始就是值
{
if(head->val==val)
{
prev=head;
head=head->next;
free(prev);
if(head==NULL)
{
return NULL;
}
}
else
{
break;
}
}
struct ListNode* cur = head;
while(cur)//从第二个开始才是value,可以使用prev,因为第一个不是value,可以存储
{
//这一部分卡了好久
if(cur->val==val)
{
prev->next=cur->next;
struct ListNode* del=cur;
free(del);
cur=prev->next;
}
else
{
prev=cur;
cur=cur->next;
}
}
return head;
}
二、链表的中间结点
leetcode链接
题目描述:
给你单链表的头结点 head
,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
思路:
用快慢指针法。
进行一个循环,先让快指针走两步,然后让慢指针走一步,直到快指针指向空或者快指针的next指向空,这时候的慢指针就指向了中间结点,并且也满足第二个结点。
代码:
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;
}
三、链表中倒数第k个结点
牛客网链接
题目描述:
输入一个链表,输出该链表中倒数第k个结点。
思路:
也是快慢指针的思想。
先让快指针走k步,然后再让快指针和慢指针一起走,直到快指针为空。
这题有一些注意细节的点,比如k大于链表结点的个数,k==0,但这些都是小细节,主要思想还是快慢指针~
代码:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(pListHead==NULL||k==0)//k=0和链表为空的情况
{
return NULL;
}
struct ListNode* fast=pListHead;
struct ListNode* slow=pListHead;
while(k--)//先让快指针走k步
{
fast=fast->next;
if(fast==NULL)
{
break;
}
}
if(k>0)//k大于链表结点的个数的情况
{
return NULL;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
四、反转链表
leetcode链接
题目描述:
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
思路:
顺序遍历链表,从第一个结点开始进行尾插,注意这里的尾插不是手撕单链表里面的pushback函数,而是应该将结点一个一个取下来。
相当于我们又学习了另外一种尾插的方式,不是直接改变头节点的值,而是将原有的头节点指向新的头节点。
代码:
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newhead=NULL;
struct ListNode* next=NULL;
//头插
while(head)
{
next=head->next;
head->next=newhead;
newhead=head;
head=next;
}
return newhead;
}
五、合并两个有序链表
leetcode链接
题目描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:
将两个链表的第一个结点顺序比较,取小的尾插到一个新的头结点上,若一个提前结束,则将另一个直接尾插到新链表上文章来源:https://www.toymoban.com/news/detail-628320.html
代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
//取小的尾插
//为何这题可以直接定义一个尾结点?
struct ListNode* newhead=NULL;
struct ListNode* tail=NULL;
while(list1 && list2)
{
if(list1->val <= list2->val)
{
if(newhead==NULL)
{
newhead=tail=list1;
//tail=newhead->next;
}
else
{
tail->next=list1;
//tail=list1->next;
tail=tail->next;
}
list1=list1->next;
}
else
{
if(newhead==NULL)
{
tail=newhead=list2;
//tail=newhead->next;
}
else
{
tail->next=list2;
tail=tail->next;
}
list2=list2->next;
}
}
if(list1)//剩余直接尾插
{
//tail=list1;
tail->next=list1;
}
if(list2)
{
//tail=list2;
tail->next=list2;
}
return newhead;
}
小心得:
在数据结构的新篇章里,注意的小细节更多,最好将能考虑的情况都要考虑到,不然调试起来比较麻烦。一般只有将头结点为空的情况下,直接赋值等于,其余一般都需要进行next链接。文章来源地址https://www.toymoban.com/news/detail-628320.html
到了这里,关于C语言单链表OJ题(较易)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!