【数据结构刷题集】链表经典习题

😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：数据结构刷题集
🔊本专栏涉及到题目是数据结构专栏的补充与应用，只更新相关题目，旨在帮助提高代码熟练度
💪种一棵树最好是十年前其次是现在

移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

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

提交一下，我们会发现执行出错。

正确代码：

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

链表的中间结点

题目链接：https://leetcode.cn/problems/middle-of-the-linked-list/description/

正确代码：

//尺取法
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

链表中倒数第k个结点

题目链接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast=pListHead,*slow=pListHead;while(k--){fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return  slow;;
}

结果代码运行不过：

正确代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast=pListHead,*slow=pListHead;while(k--){if(fast==NULL)//防止越界{return NULL;}fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return  slow;;
}

反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

法一：画图+迭代

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev,*cur,*next;prev=NULL,cur=head,next=head->next;while(cur){//反转cur->next=prev;//迭代prev=cur;cur=next;next=next->next;}return prev;
}

这个只是最基本的逻辑，一运行发现还是过不了

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev,*cur,*next;prev=NULL,cur=head,next=head->next;while(cur){//反转cur->next=prev;//迭代prev=cur;cur=next;if(next)next=next->next;}return prev;
}

再次提交，发现还是过不去：

正确代码1：

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){if(head==NULL)return NULL;struct ListNode* prev,*cur,*next;prev=NULL,cur=head,next=head->next;while(cur){//反转cur->next=prev;//迭代prev=cur;cur=next;if(next)next=next->next;}return prev;
}

法二：头插

为什么能想到头插呢？因为头插的顺序与链表的顺序刚好相反。

正确代码2：

//头插
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head, *newhead=NULL;while(cur){struct ListNode* next=cur->next;//头插cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/

法一：不带哨兵位头结点

//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1=list1,*cur2=list2;struct ListNode* head=NULL,*tail=NULL;while(cur1&&cur2){if(cur1->val<cur2->val){if(head==NULL){head=tail=cur1;}else{tail->next=cur1;tail=tail->next;}cur1=cur1->next;}else{if(head==NULL){head=tail=cur2;}else{tail->next=cur2;tail=tail->next;}cur2=cur2->next;}}if(cur1){tail->next=cur1;}if(cur2){tail->next=cur2;}return head;
}

正确代码1：

//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//如果链表为空，返回另一个if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* cur1=list1,*cur2=list2;struct ListNode* head=NULL,*tail=NULL;while(cur1&&cur2){if(cur1->val<cur2->val){if(head==NULL){head=tail=cur1;}else{tail->next=cur1;tail=tail->next;}cur1=cur1->next;}else{if(head==NULL){head=tail=cur2;}else{tail->next=cur2;tail=tail->next;}cur2=cur2->next;}}if(cur1){tail->next=cur1;}if(cur2){tail->next=cur2;}return head;
}

法二：带哨兵位头结点

正确代码2：

//带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1=list1,*cur2=list2;struct ListNode* guard=NULL,*tail=NULL;guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));tail->next=NULL;while(cur1&&cur2){if(cur1->val<cur2->val){tail->next=cur1;tail=tail->next;cur1=cur1->next;}else{tail->next=cur2;tail=tail->next;cur2=cur2->next;}}if(cur1){tail->next=cur1;}if(cur2){tail->next=cur2;}struct ListNode* head=guard->next;//防止内存泄漏free(guard);return head;
}

链表分割

题目链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;lessguard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterguard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));lesstail->next=greatertail->next=NULL;struct ListNode* cur=pHead;while(cur){if(cur->val<x){lesstail->next=cur;lesstail=lesstail->next;}else{greatertail->next=cur;greatertail=greatertail->next;}cur=cur->next;}lesstail->next=greaterguard->next;pHead=lessguard->next;free(greaterguard);free(lessguard);return pHead;}
};

运行一下：

由于牛客不提供用例错误，我们可以转到力扣官网上查。当然了，也可以把我们写的用例往代码带，看看哪出错了。

正确代码：

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;lessguard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterguard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));lesstail->next=greatertail->next=NULL;struct ListNode* cur=pHead;while(cur){if(cur->val<x){lesstail->next=cur;lesstail=lesstail->next;}else{greatertail->next=cur;greatertail=greatertail->next;}cur=cur->next;}lesstail->next=greaterguard->next;greatertail->next=NULL;//不能忽略pHead=lessguard->next;free(greaterguard);free(lessguard);return pHead;}
};

链表的回文结构

题目链接：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

正确代码：

//找中间节点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}
//反转
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur) {struct ListNode* next = cur->next;//头插cur->next = newhead;//迭代newhead = cur;cur = next;}return newhead;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* mid=middleNode(A);struct ListNode* rHead=reverseList(mid);struct ListNode* curA=A;struct ListNode* curR=rHead;while(curA&&curR){if(curA->val!=curR->val){return false;}else{curA=curA->next;curR=curR->next;}}return  true;}
};

相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

正确代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA=headA,*tailB=headB;int lenA=0,lenB=0;while(tailA){lenA++;tailA=tailA->next;}while(tailB){lenB++;tailB=tailB->next;}//不相交的情况,不写的话leetcode也不会判错if(tailA!=tailB){return NULL;}int gap=abs(lenA-lenB);struct ListNode* longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}while(gap--){longList=longList->next;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return shortList;
}

环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

正确代码：

bool hasCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

法一：双指针

正确代码1：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){//相遇struct ListNode* meetNode=slow;//公式while(meetNode!=head){meetNode=meetNode->next;head=head->next;}return head;}}return NULL;
}

法二:转化成链表相交

正确代码2：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA=headA,*tailB=headB;int lenA=0,lenB=0;while(tailA){lenA++;tailA=tailA->next;}while(tailB){lenB++;tailB=tailB->next;}//不相交的情况,不写的话leetcode也不会判错if(tailA!=tailB){return NULL;}int gap=abs(lenA-lenB);struct ListNode* longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}while(gap--){longList=longList->next;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return shortList;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){struct ListNode* meetNode=slow;struct ListNode* list1=meetNode->next;struct ListNode* list2=head;meetNode->next=NULL;return getIntersectionNode(list1,list2);}}return NULL;
}

复制带随机指针的链表

题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

正确代码：

struct Node* copyRandomList(struct Node* head) {//1.拷贝结点插入原结点的后面struct Node* cur=head;while(cur)//遍历整个链表{//插入struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node* next=cur->next;//cur copy nextcur->next=copy;copy->next=next;cur=next;}//2.拷贝random结点cur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}//3.拆组struct Node* copyHead=NULL,*copyTail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;//copy尾插if(copyHead==NULL){copyHead=copyTail=copy;}else{copyTail->next=copy;copyTail=copyTail->next;}//恢复原链表cur->next=next;cur=next;}return copyHead;
}