主页：114514的代码大冒

（欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ）

Gitee：庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com

文章目录

前言

祝你武运昌隆

一、相交链表

描述：

示例：

 思路一：
A，B两个链表的长度可能相等，也可能不相等，

如果相等，我们设置两个指针分别从A，B链表的表头开始遍历，逐个节点进行比较，如果在某个节点时，两个指针指向的地址一致且不为空，则说明发生相交

如果两个链表的长度不一致，那么我们计算出两个链表各自的长度后，比较出较长的链表，并使指向该链表的指针向前走n个节点（这个数值为两个链表的长度差）

如图：

注意：
这里是不能存在两个链表交叉的可能性的

就是如下图这种情况：

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA;struct ListNode *curB = headB;if(curA == NULL){return NULL;}if(curB == NULL){return NULL;}int num1 = 0;int num2 = 0;while (curA){num1++;curA = curA->next;}curA = headA;while (curB){num2++;curB = curB->next;}curB = headB;int n = abs(num1-num2);if(num1 > num2){while(n--){curA = curA->next;}}else{while(n--){curB =curB->next;}}while(curA && curB){if((curA == curB)&&(curA !=NULL)){return curA;}curA = curA->next;curB = curB->next;}return NULL;}

思路二:
 任然设置两个指针，分别指向两个链表的头结点，然后开始遍历，当其中一个指针走到了链表的

空节点，则从另一个链表的表头接着进行逐节点遍历，另一个指针也是如法炮制，更重要的是，在这个过程中要相互比较，一旦相等便返回该节点

如图：

这里还遗留了两个链表不想交的情况，我们利用如上图所示的办法依然能够完成我们想要的效果

 代码：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *A = headA, *B = headB;while (A != B) {A = A != nullptr ? A->next : headB;B = B != nullptr ? B->next : headA;}return A;}
};

二、旋转链表

描述：

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例：

思路：

这就相当于旋转字符串中的右旋，通过观察我们可以发现右旋n个节点就是将尾部的n个节点移动到前端

代码:
 

struct ListNode* rotateRight(struct ListNode* head, int k){struct ListNode* hd  = head;struct ListNode* cur = head;struct ListNode* prev = head;struct ListNode* fast = head;struct ListNode* slow = head;struct ListNode* p = NULL;if(hd == NULL){return NULL;}if(hd->next == NULL){return hd;}int n  = 0; while(cur){n++;if(cur->next == NULL){p = cur;}cur = cur->next;}k = k % n;if( k == 0){return hd;}while(k--){fast = fast->next;}while(fast){if(fast->next == NULL){prev = slow;}fast = fast->next;slow = slow->next;}p->next = hd;prev->next = NULL;return slow;}

三，回文链表

描述：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例一：

输入：head = [1,2,2,1]
输出：true

示例二：

 思路：

将链表均分成前后两段（奇数个节点时，忽略中间节点），然后逆置后半段链表，然后设置两个指针从前后分别同步开始遍历

代码：

bool isPalindrome(struct ListNode* head){struct ListNode* cur = head;struct ListNode* newcur = head;struct ListNode* prev = head;struct ListNode* next = head;int count = 0;int i = 1;if(head == NULL)return false;if(head->next == NULL)return true;while(cur){count++;cur = cur->next;}cur = head;while(i< (count/2 + 1)){i++;cur = cur->next;}prev = cur;next = cur->next;while(cur){cur->next = prev;prev = cur;cur = next;if(cur != NULL)next = cur->next;}i = 0;newcur = prev;cur = head;while(ival != cur->val){return false;}newcur = newcur->next;cur = cur->next;}return true;}

总结

这就是本次的全部内容了