前言:
💥🎈个人主页:Dream_Chaser～ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣和牛客上链表OJ题目
目录
一、链表中倒数第k个结点
题目描述:
解题思路:
二.合并两个链表(含哨兵位)
题目描述:
解题思路:
不含哨兵位
三.分割链表
题目描述:
解题思路:
四.链表的回文结构
题目描述:
解题思路:
一、链表中倒数第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，添加时只需要在哨兵位的头节点后面链接上新结点即可。
最后记得销毁掉这个头节点。
struct 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;
}
};
执行:
文章来源：https://www.toymoban.com/news/detail-651061.html
本篇结束，感谢你的来访。✨文章来源地址https://www.toymoban.com/news/detail-651061.html
到了这里，关于【链表OJ】链表中倒数第k个结点 合并两个链表(含哨兵位) 分割链表 链表的回文结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
