需要的请点下面：
-> 给大家推荐一款很火爆的刷题、面试求职网站 <-
文章题目来源力扣或牛客
🎈 力扣（LeetCode）全球极客挚爱的技术成长平台
LeetCode官网： https://leetcode-cn.com/problem-list/e8X3pBZi/
牛客网-笔试题库：[ https://www.nowcoder.com
]( https://www.nowcoder.com)
✨目录
1.移除链表元素
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/remove-linked-list-elements
- ✨思路一
可以依次遍历链表，将不是val值的元素尾插到新的节点中
时间复杂度：O(N)
空间复杂度：O(1)
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*newhead=NULL,*tail=NULL,*cur=head;
while(cur)
{
if(cur->val!=val)//把不是val的尾插到newhead中
{
if(tail==NULL)
{
tail=newhead=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
}
cur=cur->next;
}
//最后tail置空
if(tail!=NULL)
tail->next=NULL;
return newhead;
}
- ✨思路二
直接在原链表中删除，遇到val直接释放，让它的前一个指向val的后一个
时间复杂度：O(N)
空间复杂度：O(1)
struct ListNode* removeElements(struct ListNode* head, int val){
if(head==NULL)
return NULL;
struct ListNode*newNode=(struct ListNode*)malloc(sizeof(struct ListNode));//设置一个新的头结点
newNode->next=head;
struct ListNode*cur=newNode;
while(cur->next)
{
if((cur->next)->val==val)//删val元素
{
struct ListNode *del=cur->next;
cur->next=del->next;
free(del);
}
else
{
cur=cur->next;
}
}
cur=newNode->next;
free(newNode);
return cur;
}
2.反转链表
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/reverse-linked-list
- ✨思路一
依次遍历链表头插
时间复杂度：O(N)
空间复杂度：O(1)
struct ListNode* reverseList(struct ListNode* head){
//头插法
struct ListNode* cur=head,*next=NULL,*newhead=NULL;
while(cur)
{
next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}- ✨思路二
直接在原地修改指针指向
时间复杂度：O(N)
空间复杂度：O(1)
struct ListNode* reverseList(struct ListNode* head){
//原地修改
struct ListNode*n1=NULL,*n2=head;
while(n2)
{
struct ListNode*n3=n2->next;
n2->next=n1;
n1=n2;
n2=n3;
}
return n1;
}
3.链表的中间节点
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/middle-of-the-linked-list
- ✨思路一（不推荐）
遍历一遍求出链表长度，长度除2后，再重新让指针走中间节点
- ✨思路二（推荐）
快慢指针法，定义两个指针，fast，slow，让fast一次走两步，slow一次走一步，fast走到NULL，slow就是中间节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow=head,*fast=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
4.链表中倒数第k个结点
来源：牛客网
链接： oj链接
- ✨思路
有上题的铺垫，我们也可以用快慢指针，，定义两个指针，fast，slow，只不过这次先让fast走k步，然后fast和slow一起走，fast为NULL,slow就是倒数第K个节点
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(pListHead==NULL)
return NULL;
struct ListNode*fast=pListHead,*slow=pListHead;
while(k--)//先让fast走k步
{
//预防K很大，fast已经为空
if(fast==NULL)
return NULL;
fast=fast->next;
}
//同时走
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
5.合并两个有序链表
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/merge-two-sorted-lists
- ✨思路
依次遍历两个链表取小的尾插到新的头
时间复杂度：O(N)
空间复杂度：O(1)
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
newhead->next=NULL;
struct ListNode*cur1=list1,*cur2=list2,*tail=newhead;
while( cur1 && cur2 )//取小尾插
{
if(cur1->val > cur2->val)
{
tail->next=cur2;
cur2=cur2->next;
}
else
{
tail->next=cur1;
cur1=cur1->next;
}
tail=tail->next;
}
if(cur1)//把剩下的连上
{
tail->next=cur1;
}
if(cur2)
{
tail->next=cur2;
}
tail=newhead->next;
free(newhead);
return tail;
}
6.链表分割
来源：牛客网
链接： OJ链接
- ✨思路
遍历链表，把链表分成两条，一个全是小于x的，剩下的就是另一个链表，然后两个链表再拼接在一起
ListNode* partition(ListNode* pHead, int x) {
// write code here
//设置两个哨兵位,head1存比x大的，head2存比x小的进行尾插
struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
head1->next=NULL,head2->next=NULL;
struct ListNode* cur = pHead, * tail1 = head1, * tail2 = head2;
while(cur)
{
if(cur->val < x)//取小的尾插到head2中
{
tail2->next=cur;
tail2=tail2->next;
}
else//取大的尾插到head1中
{
tail1->next=cur;
tail1=tail1->next;
}
cur=cur->next;
}
//将两部分连接，并将尾节点的next置空
tail2->next=head1->next;
tail1->next = NULL;
pHead=head2->next;
free(head1);
free(head2);
return pHead;
}
