链表OJ刷题（二）

制作不易，三连支持一下呗！！！

文章目录

前言
一、链表的回文结构
二、相交链表
三、链表中倒数第k个节点
四、环形链表Ⅰ和Ⅱ
总结

前言

一、链表的回文结构

链表的回文结构_牛客题霸_牛客网

这里我们需要先了解一下什么叫做回文：从前向后看与从后向前看的结果是一样的，我们就称为回文结构！！！

思路：这道题目是我们之前链表OJ（一）中两道经典题目的结合------查找中间节点与链表的逆置。

我们可以先找到链表的中间节点（如果链表节点个数为偶数，有两个中间节点，我们选取靠后的那一个），然后将链表的中间节点以后的节点全部逆置。最后循环遍历原链表的前半部分和逆置得到的后半部分是否相同，如果相同就是回文结构，反之就不是。

我们只需要将这两个步骤分别实现成函数来调用即可

代码实现：

struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
typedef struct ListNode ListNode;
//查找中间节点
struct ListNode* middleNode(struct ListNode* head) {ListNode* pfast,*pslow;pfast=pslow=head;while(pfast&&pfast->next){pfast=pfast->next->next;pslow=pslow->next;}return pslow;
}
//逆置所传链表
struct ListNode* reverseList(struct ListNode* head) {if(!head){return head;}ListNode*prev,*pcur,*next;prev=NULL;pcur=head;next=head->next;while(pcur){pcur->next=prev;prev=pcur;pcur=next;if(next)next=next->next;}return prev;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereif(!A)return true;ListNode* mid=middleNode(A);mid= reverseList(mid);//循环遍历两个链表，进行比较while(mid){if(A->val!=mid->val)return false;mid=mid->next;A=A->next;}return true;}
};

二、相交链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：计算两个链表的长度

步骤：

1.先判断是否相交：

如果两个链表的尾节点相同则一定是相交的，如果连尾节点都不同，则一定不相交。

2.找到相交的起始节点：

先分别通过循环遍历的方式计算出两个链表的长度lenA和lenB，用gap来表示它们之间的差值，让长链表先遍历gap步，以保证此时链表的长度是相同的，最后循环遍历两个链表，如果出现链表A和链表B的节点是相同的，则表示这个节点就是我们要找的节点。

代码实现：

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int lenA=0,lenB=0;ListNode* curA=headA,*curB=headB;//计算链表A的长度while(curA){lenA++;curA=curA->next;}//计算链表B的长度while(curB){lenB++;curB=curB->next;}//判断尾节点是否相同if(curA!=curB){return NULL;}int gap=abs(lenA-lenB);ListNode* longlist=headA;ListNode* shortlist=headB;if(lenB>lenA){longlist=headB;shortlist=headA;}//让长链表先走gap步while(gap--){longlist=longlist->next;}//循环找相交起始节点while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

思路二：走相同的路，彼此一定会相遇

除了计算链表长度外，我们可以通过两个链表长度和相同的性质来解题

过程：遍历其中一个链表，当到末尾时跳到另一个链表继续遍历，直到再次到达末尾

1.如果链表不相交，则两个遍历指针同时指向NULL，返回NULL即可。

2.如果链表相交，因为两个遍历指针同时达到末尾，向前推理可知，两个指针一定会有同时指向相交的起始节点的时候。

3.如果两个链表等长，也会同时到达相交的起始节点。

代码实现：

这个思路实现起来就比较简洁，但是不容易想到！！！

三、链表中倒数第k个节点

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：求出链表长度，确定所求节点是第几个节点

思路非常简单

代码实现：

思路二：双指针法

受链表的中间节点一题的启发，我们这里依旧可以使用快慢指针，只需要将快慢指针的距离控制在k，当快指针走到链表末尾时，慢指针正好到达所求节点。

代码实现：

四、环形链表Ⅰ和Ⅱ

环形链表Ⅰ：

https://leetcode.cn/problems/linked-list-cycle/

思路：快慢指针法

定义一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步。如果此链表带环则，快慢两个指针一定会相遇，如果此链表不带环，则fast指针或fast->next最后一定会是NULL。

代码实现：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast=head,*slow=head;while(fast&&fast->next)//注意：顺序不能调换，否则可能会存在短路的情况{fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

接下来我们从数学的角度解释为什么两个指针一定会相遇：