目录
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;
}