【LeetCode刷题指南】--链表的回文结构详解，相交链表
🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言： 今天这篇博客博主将会详细为大家介绍一下链表的回文结构这道题，提供三种思路，其中思路二，思路三会将代码分享给大家。思路一有兴趣的朋友们可以自己去试试。
目录
1.链表的回文结构
思路一：
思路二：
思路三：
2.相交链表
1.链表的回文结构
题目链接：链表的回文结构_牛客题霸_牛客网
题目描述：
题目解读：
什么是回文结构呢，回文结构本质上来说是一种对称的数据特性，一般可以通过循环比较，反转后判断等方法来检测和处理。核心逻辑就是对称位置的元素相等，如图
思路一：
--创建新链表保存原链表所有的节点，反转新链表，比较新旧链表中的节点值是否相同，操作过程如图所示
思路二：
--创建数组(大小900)，遍历链表将节点的值依次存储在数组中，数组如果是回文结构，则链表为回文结构
注意：这种解法其实属于投机取巧的一种方法，刚好题目里面说了长度小于等于900加上牛客网上的判题并没有力扣严格，这题如果放在力扣上这种方法肯定是过不了的，因为题目还有复杂度的要求，我们这题直接定数组长度也为900其实就是卡了个bug
代码演示：
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {public: bool chkPalindrome(ListNode* A) { // write code here int arr[900]={0}; //遍历链表，将链表中节点的值依次存储到数组中 ListNode*pcur=A; int i=0; while(pcur) { arr[i++]=pcur->val; pcur=pcur->next; } //判断数组是否为回文结构 int left=0,right=i-1; while(left<right) { if(arr[left]!=arr[right]) { return false; } left++; right--; } return true; }};思路三：
--找链表中间节点，将中间节点作为新链表的头节点，反转链表后，遍历原链表和反转后链表节点，判断值是否相等
1.找链表中间节点，过程类似于下图，具体过程参考我之前的博客
代码实现 ：
//找到中间节点 ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }2.反转链表 ，过程类似于下图，具体过程参考我之前的博客
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) return NULL; ListNode*n1,*n2,*n3; n1= NULL;n2=head;n3=n2->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1;}3. 找到中间节点后，从中间节点开始反转，遍历原链表和反转之后的链表比较值是否相等
整体代码实现：
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList { public: //找到中间节点 ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } //从中间节点开始反转链表 ListNode* reverseList(ListNode* head) { if (head == NULL) return NULL; ListNode* n1, *n2, *n3; n1 = NULL; n2 = head; n3 = n2->next; while (n2) { n2->next = n1; n1 = n2; n2 = n3; if (n3) n3 = n3->next; } return n1; } bool chkPalindrome(ListNode* A) { // write code here //1.找到中间节点 ListNode* mid = middleNode(A); //2.从中间节点开始反转 ListNode* right = reverseList(mid); //3.遍历原链表和反转之后的链表比较值是否相等 ListNode* left = A; while (right) { if (right->val != left->val) { return false; } right = right->next; left = left->next; } return true; }};2.相交链表
题目链接：160. 相交链表 - 力扣（LeetCode）
题目描述：
题目描述：
思路： 求两个链表的长度，长链表先走长度差步，长短链表开始同步遍历，找相同的节点
解题过程：
1.遍历两个链表求链表长度，利用abs函数求出长度差的绝对值
2.假设长短链表，用一个if来验证，如果假设错了就修改
3.长链表先走长度差步，接着同步遍历两个链表找相同节点，找到了返回长链表或者短链表所处位置都可以
4.如果遍历完后还没有找到的话就返回NULL
具体过程图示如下：
复杂度：
- 时间复杂度: O(n)
- 空间复杂度: O(1)
代码演示：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //计算两个链表长度,求出长度差 ListNode*sizeA,*sizeB; sizeA=headA,sizeB=headB; int s1=0,s2=0; while(sizeA) { s1++; sizeA=sizeA->next; } while(sizeB) { s2++; sizeB=sizeB->next; } int s=abs(s1-s2); //假设长的和假的，用一个if验证就行 ListNode*longlist=headB; ListNode*shortlist=headA; if(s1>s2) { longlist=headA; shortlist=headB; } //长链表先走s步 while(s--) { longlist=longlist->next; } //再遍历两个链表找相同的节点 while(shortlist) { if(shortlist==longlist) return shortlist; shortlist=shortlist->next; longlist=longlist->next; } return NULL;}往期回顾：
【LeetCode刷题指南】--数组串联，合并两个有序数组，删除有序数组中的重复项
【LeetCode刷题指南特别篇】--移除链表元素，调试技巧，链表分割
【LeetCode刷题指南】--反转链表，链表的中间结点，合并两个有序链表
结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持
