数据结构-单链表-力扣题
目录
移除链表元素
题目链接：力扣（LeetCode）
思路：和前面学的单链表的中间删除数据一样，使要被删除节点的前一个节点指向下要被删除节点的下一个节点，然后把要被删除的节点free掉。
具体实现过程：先定义prev和cur，让cur指向头节点，遍历链表，如果cur->val!=val，让prev指向cur，cur指向cur的下一个节点，（prev始终在cur前面一个节点），当cur->val=val时停下，让prev的下一个节点指向cur的下一个节点，删除它们中间的cur节点，然后让cur重新指向prve->next，这就实现了节点的删除。但是还有一种情况如下图：
头节点的数据等于val，这时就需要判断了，如果头节点数据等于val，就要删除头节点，然后把head重新指向原来的头结点的下一个节点，cur重新指向head：
代码如下：
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode*prev=NULL;
struct ListNode*cur=head;
while(cur!=NULL)
{
if(cur->val==val)
{
if(prev)
{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
else
{
head=cur->next;
free(cur);
cur=head;
}
}
else
{
prev=cur;
cur=cur->next;
}
}
return head;
}这道题还有一道解法，就是重新开辟一个节点，找到不相等的节点，尾插到该节点的后面
直接上代码：
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* newhead=NULL;
struct ListNode* cur=head;
struct ListNode* tail=NULL;
while(cur!=NULL)
{
if(cur->val!=val)
{
if(newhead == NULL)
{
tail=newhead=cur;
}
else
{
tail->next = cur;
tail = cur;
}
cur=cur->next;
tail->next=NULL;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
return newhead;
}反转链表
题目链接：力扣（LeetCode）
思路：逆转链表中所有的箭头指向，如下图所示：
首先，定义n1为null，定义n2为原链表的头节点，只要使n2下一个指向的是n1，然后把n2给你，n3给n2，这样进行迭代，直到链表的所有箭头全部反转，就实现了反转链表，注意：在每次循环开始的时候都要用n3保存n2的下一个节点位置，否则，n2改变指向后就找不到后面的节点了。
代码如下：（代码中用rhead替代n1，用cur替代n2，用next替代n3）
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode*cur=head;
struct ListNode*rhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
return rhead;
}链表的中间节点
题目链接：力扣（LeetCode）
思路：定义快慢指针fast和slow，fast每次走两步，slow每次走一步，如果有奇数个节点，当fast走到最后一个节点时，slow就走到中间节点了，如果有偶数个节点，当fast走到空，slow就走到中间节点了。
因此我们在循环时要判断，当fast和fast->next为空时就不能再继续了。
代码如下：
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}返回倒数第k个节点
题目链接：力扣（LeetCode）
思路一： 上文我们讲了如何反转链表，这道题可以复用反转链表，先把链表整体反转，然后从前往后找第k个节点。
代码如下：
int kthToLast(struct ListNode* head, int k){
struct ListNode*cur=head;
struct ListNode*rhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
while(--k)
{
rhead=rhead->next;
}
return rhead->val;
}思路二： 定义快慢指针fast和slow，先让fast走k步（或者k-1步），然后slow和fast一起走，直到fast为空就停止（如果先让fast走k-1步，则当fast->next为空时停止），这时slow节点就是要找的倒数第k个节点。
fast先走k步：
int kthToLast(struct ListNode* head, int k){
struct ListNode*fast=head;
struct ListNode*slow=head;
while(k--)
{
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow->val;
}fast先走k-1步：
int kthToLast(struct ListNode* head, int k){
struct ListNode*fast=head;
struct ListNode*slow=head;
int n=k-1;
while(n--)
{
fast=fast->next;
}
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
return slow->val;
}合并两个有序列表
题目链接：力扣（LeetCode）
思路： 创建一个新链表，比较链表list1和list2中的值，每次把较小的尾插在新节点的后面（如果相等，随便取其中一个尾插），直到链表list1和list2中有一个被遍历完，就停止循环。此时，如果list1先结束，list2中有剩余的节点，直接把剩下的节点尾插到新链表后面；同理，如果list2先结束，list1中有剩余，就把list1中剩余的节点位插到新链表后面。注意：如果list1开始就为空，直接返回list2；如果list2开始就为空，直接返回list1。
代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode*newhead=NULL;
struct ListNode*tail=newhead;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
while(list1&&list2)
{
if((list1->val)<=(list2->val))
{
if(tail==NULL)
{
tail=newhead=list1;
}
else
{
tail->next=list1;
tail=tail->next;
}
list1=list1->next;
}
else
{
if(tail==NULL)
{
tail=newhead=list2;
}
else
{
tail->next=list2;
tail=tail->next;
}
list2=list2->next;
}
}
if(list1)
tail->next=list1;
if(list2)
tail->next=list2;
return newhead;
}上述代码看起来很复杂，因为在刚开始的时候，不管是list1大，还是list2大，我们都要判断新链表的头结点是不是为NULL，那如何能简化这个问题呢？
这里我们来介绍一下哨兵位的头结点，哨兵位的头结点不存储有效数据，哨兵位的头结点相当于我们新开辟的一个节点，可以直接在其后面尾插而不用担心它是不是NULL，下图就是头结点和带哨兵位的头结点之间的区别：
下面我们用哨兵位来实现一下上题：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*tail=newhead;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
while(list1&&list2)
{
if((list1->val)<=(list2->val))
{
tail->next=list1;
tail=tail->next;
list1=list1->next;
}
else
{
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
struct ListNode*del=newhead;
newhead=newhead->next;
free(del);
if(list1)
tail->next=list1;
if(list2)
tail->next=list2;
return newhead;
}这就是哨兵位的优势了，当我们用malloc开辟一个新节点newhead，就可以直接在它后面尾插，最后把newhead指向它的下一个节点，然后释放newhead就行。哨兵位的使用让我们省略了很多判断过程。
分割链表
题目链接：力扣（LeetCode）
思路：我们可以使用哨兵位的头节点，分别开辟一个“大链表”和“小链表”的头结点，把原链表中的比x小的尾插到小链表的头结点之后，把比x大的尾插到大链表的头结点之后，遍历完原链表，把大链表整体尾插到小链表后面，具体如下图：
注意：最后要将哨兵位头结点释放掉。
这道题比较复杂，分很多种情况：
1.链表为空
2.链表元素全大于x
3.链表元素全小于x
4.有大有小
代码如下：
struct ListNode* partition(struct ListNode* head, int x){
//链表为空
if(head==NULL) return NULL;
//链表全小于x
int l = 0;
struct ListNode* tmp = head;
while(tmp)
{
if(tmp->val>=x)
{
l = 1;
}
tmp = tmp->next;
}
if(l == 0)
{
return head;
}
tmp = head;
//链表全大于x
int g = 0;
while(tmp)
{
if(tmp->val<=x)
{
g = 1;
}
tmp = tmp->next;
}
if(g == 0)
{
return head;
}
struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=head;
while(cur)
{
if(cur->val<x)
{
lesstail->next=cur;
lesstail=lesstail->next;
}
else
{
greatertail->next=cur;
greatertail=greatertail->next;
}
cur=cur->next;
}
lesstail->next=greaterhead->next;
greatertail->next=NULL;
head=lesshead->next;
free(lesshead);
free(greaterhead);
return head;
}链表的回文结构
题目链接：链表的回文结构_牛客题霸_牛客网
思路：这道题可以根据上面的题目代码来实现，先找到中间节点，然后把中间节点往后的链表反转，使用双指针，指针1从头节点开始，指针2从中间节点开始，比较它们的值，如果相等，分别往后移一位，直到指针2指向空，说明就是回文结构；如果不相等，说明不是回文结构。
代码如下：
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode*fast=head;
struct ListNode*slow=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*rhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
return rhead;
}
bool chkPalindrome(ListNode* phead) {
struct ListNode*mid=middleNode(phead);
struct ListNode*rmid=reverseList(mid);
while(rmid)
{
if(phead->val==rmid->val)
{
phead=phead->next;
rmid=rmid->next;
}
else
{
return false;
}
}
return true;
}
};相交链表：找两个链表的公共节点
题目链接：力扣（LeetCode）
思路： 首先先判断它们是不是相交链表，只要判断它们的尾节点是不是相同的就行，只要尾节点相同就必定相交，因为相交链表只能是"Y"型的，不可能是"X"型的，下面就要返回相交链表的公共节点了，可以计算一下两个链表的长度，让长链表先走长度差步，然后两个链表一起走，如果有相同节点，该节点就是公共节点，如果没有，说明两个链表没有公共节点。
代码如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode*tailA=headA;
struct ListNode*tailB=headB;
int lenA=0;
int lenB=0;
while(tailA->next)
{
tailA=tailA->next;
lenA++;
}
while(tailB->next)
{
tailB=tailB->next;
lenB++;
}
if(tailA!=tailB)
{
return NULL;
}
int gap=abs(lenA-lenB);
struct ListNode*longlist=headA;
struct ListNode*shortlist=headB;
if(lenA<lenB)
{
longlist=headB;
shortlist=headA;
}
while(gap--)
{
longlist=longlist->next;
}
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}环形链表：判断链表中是否有环
题目链接：力扣（LeetCode)
思路：使用快慢指针，快指针一次走两步，慢指针一次走一步，如果有环，快指针先进环，慢指针后进环，快指针一定会某一时刻追上慢指针，此时它们相等。如果没环，快指针一定会最终指向空。
代码如下：
bool hasCycle(struct ListNode *head) {
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}环形链表 II：要求返回入环的第一个节点
题目链接：力扣（LeetCode）
思路：双指针法，一个指针从头节点处开始走，一个指针从相遇处的节点开始走，当它们相等时就是入环节点。
推导过程：
代码如下：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
struct ListNode*meet=fast;
while(head!=meet)
{
head=head->next;
meet=meet->next;
}
return meet;
}
}
return NULL;
}