【数据结构】第四站：单链表力扣题(一)

目录

一、移除链表元素

二、链表的中间结点

三、链表中倒数第k个结点

四、反转链表

五、合并两个有序链表

六、分割链表

---

一、移除链表元素

题目描述：力扣

法一：直接循环依次判断

对于这个题目，我们最容易想到的一种思路就是，直接遍历链表，当链表的值是需要删除的时候，直接删除即可，然后改变连接关系即可

代码如下

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur=head;struct ListNode* prev=NULL;while(cur!=NULL){if(cur->val!=val){prev=cur;cur=cur->next;}else {if(head==cur){head=cur->next;free(cur);cur=head;}else{struct ListNode* next=cur->next;free(cur);prev->next=next;cur=next;}}}return head;
}

对于我们写的这个代码，我们有以下几点需要注意：

1.当头结点就是需要删除的时候，那么prev是为空的，所以我们需要特殊处理，采用头删的思路即可。

2.这个函数传递的是一级指针，而非二级指针，原因是题目要求最后返回了头结点。所以可以不使用二级指针。

3.当代码出现问题，而在力扣上无法肉眼观察出错误的时候，我们就需要放到vs上进行调试，那么就涉及到需要自己手搓一个链表的问题，手搓的方法如下所示

int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;
}

法二：尾插法

这个方法的思路是这样的，我们重新定义一个链表，这个链表使用两个结点指针来控制，一个是头节点newhead,另一个是尾结点tail。一开始让他们都为空，即这个链表是空链表

然后我们在使用一个结点指针cur来遍历原来的链表，如果此处的值不是val，那就将这个结点尾插到新链表上。然后让尾结点向后走，cur结点也向后走。注意当第一个结点插入的时候，由于tail为空，所以特殊处理，直接赋值，然后使cur向后走即可

如果某处的值确实是val，那么就要设置一个新结点next去接收cur的下一个结点，然后释放cur。然后让tail的下一个结点赋值为cur。注意，这里还有一个特殊情况是，当题目所给的链表全要被删除的时候，由于tail为空，所以无法让tail的下一个结点赋值为cur。这里我们直接使用一个if排除掉这种情况即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* newhead=NULL;struct ListNode* tail=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val!=val){if(newhead==NULL){newhead=cur;tail=cur;cur=cur->next;}else {tail->next=cur;tail=cur;cur=cur->next;}}else {struct ListNode* next=cur->next;free(cur);cur=next;if(tail!=NULL)tail->next=cur;}}return newhead;
}

二、链表的中间结点

题目描述：力扣

解一：

对于这道题，我们最容易想到的思路就是，先遍历一遍，得到链表的长度，然后除2，就能得到要到达中间结点的长度。然后再一次遍历就能解出

解二：快慢指针

对于这道题，还有一种比较好的方法就是，一开始定义两个结点指针，然后一个一次走一步，另外一个一次走两步，如此一来，慢的那个指针恰好就是中间结点。具体代码如下

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

三、链表中倒数第k个结点

题目链接：链表中倒数第k个结点_牛客题霸_牛客网

对于这道题目，与第二题十分相似，也是采用快慢指针的方式，不过不同的是，这里的快慢是距离的快慢，而上一道题是速度的快慢。

这道题目的关键就是，fast应该要先走k步，然后两者再一起走，当fast为空的时候，返回慢指针即可

如果fast先走k-1步，那么fast的下一个指针为空的时候，返回慢指针

注意如果链表为空，那么直接返回空即可，如果k大于链表长度，那么就直接返回空就可以，这就意味着，fast先走的时候，每走一步都要判断一下此时fast是否为空

/*** struct ListNode {*	int val;*	struct ListNode *next;* };*//*** * @param pListHead ListNode类 * @param k int整型 * @return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{if(pListHead==NULL){return NULL;}// write code herestruct ListNode* fast = pListHead;struct ListNode* slow = pListHead;while(k--){if(fast!=NULL)fast=fast->next;elsereturn NULL;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

四、反转链表

题目描述：力扣

解一：直接改变指向

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev=NULL;struct ListNode* cur=head;while(cur!=NULL){struct ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev;
}

如上代码所示，这是最容易想到的方法，直接改变指向，我们先定义三个指针，prev，cur和next，然后使用循环依次改变指向即可

解二：头插法

这个的思路跟前面的尾插法类似， 我们可以定义一个新的链表newhead，然后将原来链表的头一个一个取出来进行头插即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur!=NULL){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

五、合并两个有序链表

题目描述：力扣

解一：尾插法

这道题目也是比较适合尾插，如果第一个链表的数据小于第二个链表的数据，那么就尾插第一个，然后cur向后移动，反之也是一样的，代码如下

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* newhead=NULL;struct ListNode* tail=NULL;while(cur1&&cur2){if((cur1->val)<(cur2->val)){if(newhead==NULL){newhead=tail=list1;cur1=cur1->next;}else{tail->next=cur1;tail=cur1;cur1=cur1->next;}}else{if(newhead==NULL){newhead=tail=list2;cur2=cur2->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}}if(cur1==NULL){tail->next=cur2;}else{tail->next=cur1;}return newhead;
}

解二：哨兵位

我们可以先创建一个哨兵位，然后利用这个哨兵位去修改解法一的代码。可以一定程度上优化代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* guard=NULL;struct ListNode* 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=cur1;cur1=cur1->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}if(cur1==NULL){tail->next=cur2;}else{tail->next=cur1;}struct ListNode* head=guard->next;free(guard);guard=NULL;return head;
}

六、分割链表

题目链接：力扣

解一：尾插法（不带哨兵位）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lesshead=NULL;struct ListNode* lesstail=NULL;struct ListNode* greaterhead=NULL;struct ListNode* greatertail=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val<x){//尾插到较小的链表if(lesshead==NULL){lesshead=lesstail=cur;cur=cur->next;}else{lesstail->next=cur;lesstail=cur;cur=cur->next;}}else{if(greaterhead==NULL){greaterhead=greatertail=cur;cur=cur->next;}else{greatertail->next=cur;greatertail=cur;cur=cur->next;         }}}if(lesshead==NULL){return greaterhead;}if(greaterhead==NULL){return lesshead;}lesstail->next=greaterhead;greatertail->next=NULL;return lesshead;
}

对于这道题，依旧采取尾插法，既然要使用尾插法，那么势必需要构建两个新链表

题目要求是将所有小于x 的值全部放在前面，且不改变顺序

那么可以使用一个链表去管理小于x 的值。同样由于是尾插，需要使用头尾两个结点来管理

然后使用另外一个链表去管理大于等于x的值，也需要使用头尾两个结点去管理

由于是尾插，那么势必涉及到链表为空，这里的链表为空状态比较复杂。如果采用哨兵位的话，确实可以避免分情况讨论了。但是这里我们选择迎难而上，不采用哨兵位的解法

既然不采用哨兵位了，那么我们现在来分析这道题，首先是定义四个结点指针，然后我们去遍历原来的链表，如果小于x，尾插到较小链表，这里要注意，如果链表为空，需要分情况讨论。

如果大于等于x，尾插到较大链表，这里也要注意，如果链表为空，也需要分情况讨论

当尾插全部完成以后。

我们还需要进行分情况讨论，如果较小链表为空，那么直接返回较大链表即可，如果较大链表为空，返回较小链表即可。

然后我们链接较小链表和较大链表，最后要注意较大链表的尾部一定要置空，否则由于尾插可能会导致出现环。代码如上所示

解二：尾插法（带哨兵位）

前面我们已经知道了不带哨兵位的方法，我们发现，分情况讨论特别繁琐。对于尾插法，如果使用哨兵位，就可以直接无视掉所有的分情况讨论。而大体思路却不会变化太多，下面是代码。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lessGuard=NULL;struct ListNode* lesstail=NULL;struct ListNode* greaterGuard=NULL;struct ListNode* greatertail=NULL;lessGuard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterGuard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));greatertail->next=NULL;lesstail->next=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val<x){lesstail->next=cur;lesstail=cur;cur=cur->next;}else{greatertail->next=cur;greatertail=cur;cur=cur->next;         }}lesstail->next=greaterGuard->next;greatertail->next=NULL;head=lessGuard->next;free(lessGuard);free(greaterGuard);lessGuard=greaterGuard=NULL;return head;
}

这里我们有一点需要特别注意，一定要让greatertail->next置为空，否则会陷入死循环，这也是使用哨兵位就需要做的一些细节，一旦使用哨兵位，一定要注意一些细节

---

本小节内容就到这里了，欲知后事请看下节

如果对你有帮助的话，一定要点赞加收藏哦！！！