前言:
💥🎈个人主页:Dream_Chaser～ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣和牛客上链表OJ题目
一、链表中倒数第k个结点
来源:链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
题目描述:
输入一个链表，输出该链表中倒数第k个结点。
示例:
输入:1,{1,2,3,4,5}
返回值:{5}
解题思路:
- 创建两个指针，一个名为fast(快指针),另一个则是slow(慢指针),同时把头结点的地址赋值给二者，也就意味着两个指针同时指向头结点。
- 通过传参传过来的参数k的含义是该链表中倒数的第k个结点
- 进入第一个while循环中，k--多少次也就意味着fast指针先走k步
- 接着进入第二个while循环，以fast!=NULL为循环的条件
- 接着两指针一起走相同的步数,待fast指向NULL结束，此时正好是slow指向的链表中倒数第k个结点
- 返回slow指针
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast = pListHead, * slow = pListHead; while (k--) { if (fast == NULL)// 快慢指针同时移动，直到快指针到达链表末尾 { return NULL; } fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow;// 返回慢指针所指向的节点 }
动图解析:
执行:
二.合并两个链表(含哨兵位)
此题来源:21. 合并两个有序链表 - 力扣（LeetCode）
题目描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
输入:
l1 = [1,2,4], l2 = [1,3,4]
输出:
[1,1,2,3,4,4]
解题思路:
主要思路跟这篇的思路相差不大
不含哨兵位
二级指针解法请看->【链表OJ 5】合并两个有序链表_Dream_Chaser～的博客-CSDN博客
唯一区别如下:
首先,malloc一个哨兵位的头节点,
接着创建两个指针:head和tail，并让它们指向哨兵位的头节点。
注意:
此头结点不存储任何数据，使用时不用判断tail指针指向的结点是否为NULL，因为tail指向的哨兵位绝对不为NULL，添加时只需要在哨兵位的头节点后面链接上新结点即可。
最后记得销毁掉这个头节点。
1. struct Listruct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) return list2; if(list2 ==NULL) return list1; struct ListNode*head=NULL,*tail=NULL; head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); while(list1 && list2) { if(list1->val < list2->val) { //不用判断tail是否指向NULL，需要的时候直接在tail后面链接即可 tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } //记得销毁哨兵位的头节点 struct ListNode* del=head; head=head->next; free(del); return head;//链表的第一个有效的结点 }
执行:
三.分割链表
来源:链表分割_牛客题霸_牛客网 (nowcoder.com)
题目描述:
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
示例:假定x为5
输入:原链表顺序
输出:返回链表
解题思路:
1.创建两个带头结点(这题一定要含哨兵位，不然很麻烦)的单链表
1️⃣lesshead:指向比x值小的链表的哨兵位(第一个链表)
2️⃣lesstail：用于遍历第一个链表(比x小的)，以及链接比x值小的结点，最后待cur指向NULL时，链接到greaterhead，将两个链表链接起来
3️⃣greaterhead:指向比x值大的链表的哨兵位(第二个链表),与lesstail链接起来
4️⃣greatertail:用于遍历第二个链表(比x大的),以及链接比x值大的结点，最后一定要把greatertail置空，因为在原链表中，greatertail指向的这个值还存着下一个结点的地址，它的next有可能是NULL，也有可能不是NULL
如果greatertail指向的这个值不为NULL，若此时不置空，则会出现环状链表的情况。
2.cur用于遍历原始链表是否结束的条件，若cur不指向NULL，则遍历原始链表，若指向NULL，则表示lesshead与greaterhead指向的两个链表尾插完毕。
3.判断
比x小的，用lesstail访问哨兵位的next与cur指向的当前结点链接起来，之后
lesstail=lesstail->next, 准备尾插第二个结点。
比x大的，用greatertail访问哨兵位的next与cur指向的当前结点链接起来，之后greatertail=greatertail->next, 准备尾插第二个结点。
4.接着待两个链表尾插结束，要记得lesstail的next与greaterhead->head链接起来，接着greatertail置空。
5.然后原始链表头结点pHead要用lesshead->next赋值向后更新一位，此时才是改变后的链表的头结点。
6.将两个哨兵位free掉，接着返回pHead，打印链表。
初始情况：
动图解析:
最终的情况：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { 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=pHead; 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; pHead=lesshead->next; free(lesshead); free(greaterhead); return pHead; } };
执行:
四.链表的回文结构
来源:LCR 027. 回文链表 - 力扣（LeetCode）
题目描述:
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入:head = [1,2,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
解题思路:
先找到中间结点，然后将中间结点mid指向的链表反方向输出,接着用原链表头结点head指向的前半段与反向后的链表头结点rmid指向的后半段进行比较。
顺序:
1.用快慢指针方法找到链表的中间结点,这是前半段:http://t.csdn.cn/YH93S
2.用中间结点mid指向的链表反转,这是后半段，反转链表:http://t.csdn.cn/rf9Jl
3. 比较链表的前半段和后半段
若相等，则是回文结构(返回true)
否则，不为回文结构(返回false)
动图解析:
这里省略了反转链表的细节过程，若有需要可以看看上面的那篇文章。
//c++环境下c适用 class Solution { public: struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head, *rhead = NULL; while (cur) { struct ListNode* next = cur->next; //头插 cur->next = rhead; rhead = cur; //迭代 cur = next; } return rhead; } bool isPalindrome(struct ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rmid = reverseList(mid); while (rmid) { if (rmid->val != head->val) { return false; } else { rmid = rmid->next; head = head->next; } } return true; } };
执行:
本篇结束，感谢你的来访。✨
