单链表经典算法题理解

目录

1. 前言：

2. 移除链表元素

3.  反转链表

4. 合并两个有序链表

5. 链表的中间节点

6. 环形链表的约瑟夫问题

7. 分割链表

---

1. 前言：

当我们学习了单链表之后，我能可以尝试的刷一下题了，以下分享一下几道题的解法

2. 移除链表元素

题目链接：. - 力扣（LeetCode）

思路：

我们这里可以通过创建一个新链表的形式，用来接收原链表里面不等于val的值，把他拿下来尾插，这里题目规定了原链表的值可能是0，就表示原链表是空链表，那我们进行判断，如果原链表为空，我们直接将原链表返回去，如果不为空，我们就进行遍历原链表，来判断原链表的值是否等于给定的val，然后拿下来在新链表中进行尾插操作，最后，判断一下新链表的尾是否是空的，如果不是空，我们需要将它手动置空，最后我们返回新链表的头即可。

代码

 typedef struct ListNode sln;//类型重命名，简化写法
struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)//如果链表为空，我们直接将原链表返回去{return head;}else{//我们创建新链表sln* newnode = NULL;sln* ptail = NULL;//创建一个指针用来遍历原链表sln*pcur = head;while(pcur){//如果原链表里面的值不等于val，我们就拿下来尾插if(pcur->val != val){//如果新链表为空，此时，这个链表的头和尾就都是拿下来的数据if(newnode == NULL){newnode = pcur;ptail = pcur;}else{//链表不为空，进行尾插ptail->next = pcur;ptail = ptail->next;}}pcur = pcur->next;}if(ptail)//这里判断，ptail是否是空节点，如果不是，我们需要将它指向空ptail->next = NULL;//返回新链表的头return newnode;}
}

3.  反转链表

题目：. - 力扣（LeetCode）

思路：

其实这里我们看到这个题目的时候，首先肯定是想到的是创建一个新链表，将原链表的节点拿下来一个个头插，但是这个方法写起来有点麻烦，我们这里用到一个新的方法来解，就是定义三个p1，p2和p3指针，分别指向空，头节点，和头节点下一个节点，将p2指向p1之后，将他们3个指针都往后移动，最后p2走到空了的话，p1此时就是头节点了，直接返回p1.

代码

 typedef struct ListNode sln;//类型重命名 简化写法
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL)//判断链表是否为空{//如果为空直接返回原链表return head;}//定义三个指针，分别指向空，头节点和头节点下一个节点sln* p1 = NULL;sln* p2 = head;sln* p3 = head->next;while(p2)//当p2走到空了说明p1是头节点{p2->next = p1;p1 = p2;p2 = p3;if(p3 != NULL)//增加一个判断条件，如果p3走到空了，我们访问p3就会出错p3 = p3->next;}//直接返回p1return p1;
}

4. 合并两个有序链表

题目：. - 力扣（LeetCode）

思路：

这个题目，我能可以使用创建新链表的方式来解决，我们先创建一个新链表，然后再创建两个指针，分别用来遍历原链表里面的数据，如果1链表里的节点数据小于2链表里的节点数据，我们就把它拿下来尾插到新链表，反之将2链表里面的数据拿下来了尾插到新链表里面，

但是我们要考虑两种情况，就是如果1链表已经遍历完了，但是2链表里面还有数据，那么我们就将2链表里面的数据拿下来了尾插到新链表里面，反之将1链表里面的数据尾插到新链表中。

代码

 typedef struct ListNode sln;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){//如果list1为空链表，直接返回list2return list2;}if(list2 == NULL){//如果list2为空链表，直接返回list1return list1;}//创建新链表sln* newnode = (sln*)malloc(sizeof(sln));sln* ptail = newnode;//定义两个指针，分别指向两个链表的头节点sln* p1 = list1;sln* p2 = list2;//循环遍历两个链表while(p1&&p2){//如果p1<p2if(p1->val<p2->val){//把p1拿下来尾插，p1向后走ptail->next = p1;ptail = ptail->next;p1 = p1->next;}else{//把p2拿下来尾插，p2往后走ptail->next =p2;ptail = ptail->next;p2 = p2->next;}}//可能p2走到空了，p1里面还有元素if(p1){//拿下来尾插ptail->next = p1;ptail = ptail->next;}if(p2)//可能p1走到空了，p2里面还有元素{//拿下来尾插ptail->next =p2;ptail = ptail->next;}sln* ret = newnode->next;free(newnode);//动态申请的空间，手动释放newnode = NULL;return ret;
}

5. 链表的中间节点

题目：. - 力扣（LeetCode）

思路：

我们要找到链表的中间节点，我们可以采取计数器的方法，先遍历一遍链表，然后取计数器的中间值，在遍历一遍链表，返回中间值时的节点，这样也可以解题，但是需要遍历两遍链表，比较麻烦。那么我们就采取另一种方法。

快慢指针的方法。

我们定义两个指针，让他们遍历链表，但是两个指针的移动速度不一样，快指针一次走两步，慢指针一次走1步，这样，当快指针遍历完链表或者走到链表的尾节点时，此时慢指针就刚好走到链表的中间节点位置，直接返回慢指针指向的节点，这样就可以找到链表的中间节点了

代码：

 typedef struct ListNode sln;
struct ListNode* middleNode(struct ListNode* head) {//我们定义两个指针sln* slow = head;sln* fast = head;while(fast&&fast->next!=NULL){//让这两个直接按照不同的速度往后走//2*slow = fastslow = slow->next;fast = fast->next->next;}return slow;
}

6. 环形链表的约瑟夫问题

题目： 环形链表的约瑟夫问题_牛客题霸_牛客网

什么是约瑟夫问题呢？

来自百度：

 思路：

这里，我们知道报到指定数目，指定数目的人就要离开，我们首先需要定义一个计数器，然后我们需要使用到两个指针，一个指针用来遍历链表，一个指针记录住遍历链表的指针的上一次节点，然后循环遍历链表，直到链表只剩最后一个节点，跳出循环，返回最后一个节点里面的值就可以了。

代码:

 typedef struct ListNode sln;
//创建节点sln* BuyNode(int x){sln* newnode = (sln*)malloc(sizeof(sln));if(newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;}//创建带环链表sln * CircleNode(int x){sln* newnode = BuyNode(1);sln* ptail = newnode;for(int i = 2;i <= x;i++){ptail->next = BuyNode(i);ptail = ptail->next;}ptail->next = newnode;return ptail;}int ysf(int n, int m ) {//创建一个指针指向头节点sln*prev = CircleNode(n);//创建一个指针指向头节点的前一个节点sln*phead = prev->next;// write code hereint count = 1;//定义计数器while(phead->next!= phead)//链表如果只有一个节点就跳出循环{if(count == m)//当计数器==给定数目时，需要删除节点{prev->next = phead->next;free(phead);phead = prev->next;count = 1;}else //不==，让两个指针都往后，计数器++{prev = phead;phead = phead->next;count++;}       }//返回最后一个节点里面的数据return phead->val;
}

7. 分割链表

题目：. - 力扣（LeetCode）

思路：

这里我们可以采取创建两个新链表的形式，一个用来接收小于x的节点，另一个用来接收大于或等于x的节点。然后将两个链表首尾链接的方式，并且将用头节点连接的尾节点指向空。

代码：

typedef struct ListNode sln;
struct ListNode* partition(struct ListNode* head, int x){if(head == NULL)//判断原链表是否为空{return head;}//创建一个指针来遍历原链表sln*pcur = head;//这里创建一个大链表来就收原链表大于x的节点sln*large = (sln*)malloc(sizeof(sln));sln* ptail = large;//创建一个小链表来接收原链表小于x的节点sln* little = (sln*)malloc(sizeof(sln));sln*pend = little;while(pcur){if(pcur->val<x){pend->next = pcur;pend = pend->next;}else{ptail->next = pcur;ptail = ptail->next;}pcur = pcur->next;}//遍历完原链表//将大小链表连接，将大链表尾节点指向空ptail->next = NULL;pend->next =large->next;//释放申请的空间sln*ret = little->next;free(little);free(large);little = large = NULL;return ret;
}