【LeetCode牛客数据结构】单链表的应用
🔥个人主页：胡萝卜3.0
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题
⭐️人生格言：不试试怎么知道自己行不行
目录
一、移除链表元素
1、题目描述
2、思路及代码
二、反转链表
1、题目描述
2、思路及代码
三、链表的中间结点
1、题目描述
2、思路及代码
四、合并两个有序链表
1、题目描述
2、思路及代码
五、链表的回文结构
1、题目描述
2、思路及代码
六、相交链表
1、题目描述
2、思路及代码
一、移除链表元素
203. 移除链表元素 - 力扣（LeetCode）
1、题目描述
2、思路及代码
思路1：查找值为val的结点并返回该结点，删除指定位置上的结点
思路2：创建新链表，遍历原链表，将不为val的值尾插到新链表中
思路2转换成代码：
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead=NULL;ListNode* newTail=NULL;//遍历链表，将不为val的结点尾插到新链表中ListNode* pcur=head;while(pcur!=NULL){if(pcur->val!=val){//尾插if(newhead==NULL){newhead=newTail=pcur;}else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;}if(newTail!=NULL){newTail->next=NULL;}return newhead;
}时间复杂度为：O（N） 空间复杂度为：O（1）
二、反转链表
206. 反转链表 - 力扣（LeetCode）
1、题目描述
2、思路及代码
思路1：创建新链表，遍历原链表，遍历到一个结点就头插到新链表中
将上面思路转换成代码：
//遍历链表，头插typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* newhead=NULL;ListNode* pcur=head;while(pcur!=NULL){ListNode* next=pcur->next;pcur->next=newhead;newhead=pcur;pcur=next;}return newhead;
}时间复杂度为：O（N） 空间复杂度为：O（1）
思路2：创建三个指针，改变指针的指向
将上面思路转换成代码：
//思路2创建三个指针typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL){return head;}ListNode* n1,*n2,*n3;n1=NULL;n2=head;n3=n2->next;while(n2!=NULL){n2->next=n1;n1=n2;n2=n3;if(n3!=NULL)n3=n3->next;}return n1;
}时间复杂度为：O（N） 空间复杂度为：O（1）
三、链表的中间结点
876. 链表的中间结点 - 力扣（LeetCode）
1、题目描述
2、思路及代码
思路1：遍历链表，求出链表的结点个数size，size/2为中间结点的个数，循环找中间结点，最后返回中间结点。
将上面的思路转换成代码：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//遍历求出结点个数ListNode* pcur=head;int size=0;while(pcur!=NULL){size++;pcur=pcur->next;}int mid=size/2;pcur=head;while(mid--){pcur=pcur->next;}return pcur;
}时间复杂度为：O（N） 空间复杂度为：O（1）
思路2：创建快慢指针，快指针走两步，慢指针走一步，最终返回慢指针所在的结点位置
将上面的思路转换成代码：
//快慢指针typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}时间复杂度为：O（N） 空间复杂度为：O（1）
四、合并两个有序链表
21. 合并两个有序链表 - 力扣（LeetCode）
1、题目描述
2、思路及代码
思路：创建新链表，遍历两个链表，比较大小，小的往新链表中尾插
将上面思路转换成代码：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* newhead,*newtail;newhead=newtail=NULL;ListNode* l1=list1;ListNode* l2=list2;while(l1&&l2){if(l1->val>l2->val){//较小的尾插if(newhead==NULL){newhead=newtail=l2;}else{newtail->next=l2;newtail=newtail->next;}l2=l2->next;}else{if(newhead==NULL){newhead=newtail=l1;}else{newtail->next=l1;newtail=newtail->next;}l1=l1->next;}}//跳出循环，需要判断那个链表没有遍历完if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead;
}有没有uu发现上面的代码有点冗余，我们对上面的代码改进一下：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* newhead,*newtail;newhead=newtail=(ListNode*)malloc(sizeof(ListNode));ListNode* l1=list1;ListNode* l2=list2;while(l1&&l2){if(l1->val>l2->val){//较小的尾插newtail->next=l2;newtail=newtail->next;l2=l2->next;}else{newtail->next=l1;newtail=newtail->next;l1=l1->next;}}//跳出循环，需要判断那个链表没有遍历完if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead->next;
}五、链表的回文结构
链表的回文结构_牛客题霸_牛客网
1、题目描述
2、思路及代码
思路1：创建新链表保存原链表所有的节点，反转新链表，比较新旧链表中的节点的值是否相同
将上面思路转换成代码：
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereListNode* pcur=A;//反转pcur链表ListNode* n1,*n2,*n3;n1=NULL;n2=pcur;n3=n2->next;while(n2!=NULL){n2->next=n1;n1=n2;n2=n3;n3=n3->next;}//n1为反转后链表的头结点while(n1!=NULL&&pcur!=NULL){if(n1->val!=pcur->val){return false;}n1=n1->next;pcur=pcur->next;}return true;}
};思路2：题目中写到链表的长度不超过900，创建数组（大小不超过900），遍历链表，将链表中的值放入数组中，若数组为回文结构，那链表就为回文结构。
将上面思路转换成代码：
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint arr[900];//遍历链表ListNode* pcur=A;int i=0;while(pcur){arr[i++]=pcur->val;pcur=pcur->next;}int left=0;int right=i-1;while(left<right){if(arr[left]!=arr[right]){return false;}left++;right--;}return true;}
};思路3（最正确的解法）：找链表的中间节点，将中间节点作为新链表的头结点，反转新链表，遍历原链表和新链表，看对应的值是否相等。
将上面思路转换成代码：
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereListNode* pcur=A;//找链表的中间节点ListNode* slow=pcur;ListNode* fast=pcur;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}//slow为中间节点//反转ListNode* n1,*n2,*n3;n1=NULL,n2=slow,n3=n2->next;while(n2!=NULL){n2->next=n1;n1=n2;n2=n3;n3=n3->next;}//比较原链表和反转之后的链表while(n1!=NULL){if(n1->val!=pcur->val){return false;}n1=n1->next;pcur=pcur->next;}return true;}
};六、相交链表
160. 相交链表 - 力扣（LeetCode）
1、题目描述
2、思路及代码
思路：遍历两个链表，求出两个链表的长度，然后做差，得到长度差。比较两个链表的长度，得到较长的链表（这里可以使用假设法），先让较长链表走长度差步，然后两个链表同时走，比较对应结点的内容，如果相等，则说明相遇，返回该结点；如果遍历完，还没有相遇，则直接返回NULL。
将上面思路转换成代码：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//遍历链表，求出两个链表的长度ListNode* pa=headA;ListNode* pb=headB;int sizea=0,sizeb=0;while(pa!=NULL){sizea++;pa=pa->next;}while(pb!=NULL){sizeb++;pb=pb->next;}//得到长链表的头节点ListNode* shortlist=headA;ListNode* longlist=headB;if(sizea>sizeb){shortlist=headB;longlist=headA;}//先让长链表走长度差步int size=abs(sizea-sizeb);while(size--){longlist=longlist->next;}//现在让两个链表同时走while(longlist!=NULL&&shortlist!=NULL){if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}return NULL;
}ok，本次单链表的相关OJ题就介绍到这，后面还会有更多的题目等着我们继续攻克！！！