【c数据结构】OJ练习篇 帮你更深层次理解链表！（相交链表、相交链表、环形链表、环形链表之寻找环形入口点、判断链表是否是回文结构、 随机链表的复制）

目录

一. 相交链表

二. 环形链表

三. 环形链表之寻找环形入口点

四. 判断链表是否是回文结构

五. 随机链表的复制

---

一. 相交链表

最简单粗暴的思路，遍历两个链表，分别寻找是否有相同的对应的结点。

1. 我们对两个链表的每个对应的节点进行判断比较，如果不相等的话

2. 那么我们就进行换下一对节点进行判断

但这里存在一个弊端，两条链表可能有一条长，一条短，存在节点数不一样的情况，挨个比较。

举例来说，只是举例来说：

• 假设一个链表是6个节点，一个是8个节点，那么差值就是8

• 那么我们让长的那个链表优先走 | 8-6 | 步，走后两个链表长度一致，就能开始进行比较了

• 解决这个问题很简单--> 遍历计算两个链表长度求差，让长的先走完差值步，使两条链表长度一致。 

于是思路有，步骤有√

1. 求差求两个链表长度差值
2. 让长的链表先走差值步
3.  遍历两个链表，分别对应是否指向相同的结点

/*** 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) {//1. 遍历两个链表，求他们的长度差//设置两个链表头结点，方便遍历ListNode* l1 = headA;ListNode* l2 = headB;//设置变量存放链表长度，方便求差int sizeA=0,sizeB=0;//遍历计算两条链表长度ingwhile(l1){sizeA++;l1 = l1->next;}while(l2){sizeB++;l2 = l2->next;}//求长度差int gap = abs(sizeA-sizeB);//abs 绝对值函数//2.长链表先走长度差步//由于不知道哪个链表长，先随便定义再判断ListNode* longList = headB;ListNode* shortList = headA;if(sizeA > sizeB){longList = headA;shortList = headB;}//长链表先走while(gap--){longList = longList->next;}//此时的longList和shortList在同一起跑线//3. 遍历两个链表，要么相交，要么不相交while(longList && shortList)//条件是两个链表都不得是空{if(longList == shortList)//找到相同结点，相交{return longList;//反正相同结点，返回long 和short 都一样}//不相同，换下一结点继续比较longList = longList->next;shortList = shortList->next;}return NULL;//循环结束，可见不相交，返回空}

二. 环形链表

类似追击问题，若快指针在追慢指针的时候追到了，说明链表带环

 

如果链表不是带环的，那么快慢指针是绝对不会相遇的

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//创建快慢指针ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){//慢指针走一步，快指针走两步，相当于快在一步一步追慢slow = slow ->next;fast = fast ->next->next;//相遇，说明带环if(fast == slow){return true;}}return false;
}

三. 环形链表之寻找环形入口点

假设meet为快慢指针相遇点

 

遍历头结点pcur和meet,因为环形，终将相遇

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//1. 找快慢指针相遇点->说明是环形结点ListNode* slow = head;ListNode* fast = head;while(fast && fast ->next){slow = slow ->next;fast = fast ->next->next;if(fast == slow)//找到相遇点！是环形{//2. 遍历头结点和快慢指针相遇点，每次一步，其相遇点就是环形入环第一个结点ListNode* pcur = head; //定义头结点while(pcur != fast){//但凡是环形，肯定会相遇pcur = pcur ->next;fast = fast ->next;}return pcur;}}return NULL;
}

四. 判断链表是否是回文结构

 

先找中间结点（快慢指针）

再将中间结点之后的链表反转，最后链表左右进行比较看是否相同

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//1. 找中间结点ListNode* slow = A;ListNode* fast = A;while(fast &&fast->next){slow = slow->next;fast = fast->next->next;}ListNode* mid = slow;//2. 根据中间结点反转后面的链表ListNode* n1 = NULL;//指向空ListNode* n2 = mid;//指向中间结点ListNode* n3 = n2->next;//指向n2的下一个结点while(n2){n2->next = n1;//n2指向其前一个结点（初始是空）n1 = n2;//n1往后走n2 = n3;//n2往后走if(n3)//前提：n3不得为空，n3才能继续往后走n3 = n3->next;//n3往后走}ListNode* right =n1;//n1为我反转链表的头结点//3. 比较原链表和反转链表的结点ListNode* left = A;//原链表头结点while(right)//反转链表的尾结点是指向空的，当其走到空，说明遍历完了{if(left->val != right->val){//有不相等的值，说明不回文return false;}left = left->next;right = right->next;}return true;}
};

五. 随机链表的复制

思路：

原链表上复制并插入复制结点

赋值random

断开链表

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
//复制链表结点
Node* buynode(int x){Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}
//将复制的新链表插入原链表
void AddNode(Node* head){Node* pcur = head;//头结点while(pcur){Node* Next = pcur->next;//原链表的下一结点Node* newnode = buynode(pcur->val);//要复制的新结点newnode->next = Next;pcur->next = newnode;pcur = Next;//pcur走到下一结点}}struct Node* copyRandomList(struct Node* head) {if(head == NULL){return NULL;}//1. 原链表上复制结点//此时链表是 node1 -> newcopy1 -> node2 -> newcopy2-> node3..AddNode(head);//2. 赋值randomNode* pcur = head;while(pcur){//循环修改random指针Node* copy = pcur->next;//此时pcur的下一结点即上一步插入的复制结点if(pcur->random != NULL){//因为创建新的节点时，直接让random指向空，现在只需将原链表中random不指向空的进行处理copy->random = pcur->random->next;}pcur = copy->next;//copy下一结点为原链表的下一结点}//3. 断开链表pcur = head;//让pcur回到头结点Node* newhead,*newtail;//为新链表创建头结点和要遍历连接的结点newhead = newtail = pcur->next;//pcur下一结点就是复制的新链表的头结点while(pcur->next->next)//因为有多插入复制的，所以pcur->next->next才是原链表下一结点{pcur = pcur->next->next;//pcur走到原链表下一结点newtail->next = pcur->next;//新链表连接新链表（被复制的）下一结点newtail = newtail->next;//新链表往后走}return newhead;//返回新链表头结点
}

 希望对你有帮助