【数据结构篇】~链表算法题1（含快慢指针的解析）

前言

关于环形指针与快慢指针是算法题中的常客，如果能掌握将是我们的一大助力！

1.快慢指针

1 移除链表元素​

https://leetcode.cn/problems/remove-linked-list-elements/description/

1）思路

这道题可以用一个新链表来保存原链表中不是val的值，最后返回新链表的头节点就行。给一个newhead和ptail（作用：用来走链表），给一个purc用来遍历原链表以找到不是val的节点。

2）解析

 typedef struct ListNode slnode;
struct ListNode* removeElements(struct ListNode* head, int val) {slnode*newhead = NULL;slnode*ptail = NULL;slnode* purc=head;if(head==NULL)//给的原链表是空链表时{return NULL;} else//不是空链表{       while(purc){             if(purc->val != val)//当purc中的数据不是val时就''尾插''{if(newhead==NULL)//处理第一个不是val的节点{newhead=ptail=purc;}else//新链表有了第一个节点{ptail->next=purc;ptail=ptail->next;}}purc=purc->next;}if(ptail)//为了断开和原链表的链接ptail->next=NULL;return newhead;}
}

2 反转链表​

https://leetcode.cn/problems/reverse-linked-list/description/​

1)思路

反转链表整体来说是比较简单的。创建三个指针就能解决，
n1置为null，n2置为原链表的头指针，n3置为head->next，然后开始循环让n2指向n1，把n1给n2，n2给n3，n3给n3->next,知道n2为空时，n1就是新链表的头节点。

2解析

 typedef struct ListNode slnode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)//如果处理的是空链表{return NULL;}else//不是空链表{slnode* n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)//如果n3已经走到null，n3就不用走了n3=n2->next;}return n1;}
}

3 链表的中间结点​（快慢指针）

https://leetcode.cn/problems/middle-of-the-linked-list/description/​

1）思路

这道题经典的快慢指针，创建一个快指针，和一个慢指针，开始时两个指针都指向头节点，随后慢指针走一步快指针走两步，当快指针走到最后一个节点（链表有奇数个节点）或者为空时（链表有偶数个节点）慢指针就走到了中间节点

2）解析

typedef struct ListNode slnode;
struct ListNode* middleNode(struct ListNode* head) {slnode* quick=head;slnode* slow=head;if(head==NULL)//处理空链表{return NULL;}else{while(quick && quick->next)//这里quick不能为空，（是为了处理偶数个结点的情况）{ slow=slow->next;quick=quick->next->next;//慢指针走一步，快指针走两步}return slow;}
}

4 合并两个有序链表​

https://leetcode.cn/problems/merge-two-sorted-lists/description/​

1）思路

这道题与之前的合并有序数组思路大致一致！
合并有序数组大家可以去看一看

2）解析

typedef struct ListNode slnode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL)//处理空链表{return list2;}else if(list2==NULL){return list1;}else//没有空链表{ slnode* newhead = NULL;slnode* newtail = NULL;while(list1 && list2){if(list1->val > list2->val)//比较,{if(newhead==NULL)//处理第一个节点{newhead=newtail=list2;  list2=list2->next;}else{newtail->next=list2;newtail=newtail->next;list2=list2->next;}}else{if(newhead==NULL)//处理第一个节点{newhead=newtail=list1;list1=list1->next;}else{newtail->next=list1;newtail=newtail->next;list1=list1->next;}}        }//处理有链表提前轮空if(list1)newtail->next=list1;if(list2)newtail->next=list2;return newhead;}
}

5 链表分割​

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

1）思路

创建两个新链表，一个放小于x的数据，一个放大于x的数据，最后连接两个链表

2）解析

#include <cstddef>
class Partition {
public:ListNode* partition(ListNode* pHead, int x){// write code hereListNode*lesshead,*lesstail,*bighead,*bigtail;lesshead  = lesstail = (ListNode*)malloc(sizeof(ListNode));//充当哨兵位bighead   = bigtail  = (ListNode*)malloc(sizeof(ListNode));ListNode*purc=pHead;while(purc){            if(purc->val < x)//放到小链表里{lesstail->next=purc;lesstail=lesstail->next;       }else//放到大链表里{bigtail->next=purc;bigtail=bigtail->next;}purc = purc->next;}bigtail->next=NULL;//防止形成环形链表成死循环lesstail->next=bighead->next;//连接大小链表ListNode* ret=lesshead->next;free(lesshead);free(bighead);lesshead=bighead=NULL;return ret;}
};