数据结构|LeetCode每日一刷 --- 手撕单链表习题（2）数据结构|链表|c语言

目录
1、链表的回文结构
2、相交链表
3、复制带随机指针的链表
1、链表的回文结构

链接直达：

链表的回文结构

题目：

文章图片

思路：

找中间节点再逆置，此法非常巧妙，找中间节点和逆置这两块内容在上一份博文中已经详细讲解过，这里不多赘述，这样做的原因是执行上述操作后遍历原头节点和逆置后新头节点，判断值是否相等，若遍历后都相等则返回true，反之false。

文章图片

代码如下：

class PalindromeList { public: //第一步：找到中间节点 struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } //第二部：逆置从中间节点开始往后的数据，并返回新的头节点 struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) { return NULL; } struct ListNode* n1 = head; struct ListNode* n2 = head->next; struct ListNode* n3 = NULL; while (n1) { n1->next = n3; n3 = n1; n1 = n2; if (n2) { n2 = n2->next; } } return n3; }bool chkPalindrome(ListNode* A) { // write code here struct ListNode* mid = middleNode(A); struct ListNode* rHead = reverseList(mid); while (A && rHead) { if (A->val == rHead->val) { A = A->next; rHead = rHead->next; } else { return false; } } return true; } };

2、相交链表

链接直达：

相交链表

题目：

文章图片

思路：

法一：A链表的每个元素跟B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。
【数据结构|LeetCode每日一刷 --- 手撕单链表习题（2）】此法的时间复杂度是O(M*N)，此法的优势就是在判断好是否相交后直接把相交的节点求出来了，注意：在比较的时候不能拿值去比较，要拿地址去比较。此法的缺陷就是效率相对较低，可以再进行改进。
法二：遍历原链表 + 快慢指针
先判断两个链表是否相交
依次遍历两个链表到尾，看两个尾节点地址是否相同，若相同则一定相交。此时的时间复杂度就是O(M+N)，相较于法一可是优化了太多。
再找出第一个交点
执行完上一步知道了链表相交，接下来就要求交点了，先求出两个链表的长度La，Lb。再定义连个指针分别指向两个链表的头，让长度较长的链表指针先走 | La-Lb | 步，再让两个链表指针一起走，若发现地址存在相同，那么就停止，此时找到交点。这种情况的时间复杂度同样是O(M+N)。

文章图片

代码如下：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { int lenA = 0; int lenB = 0; struct ListNode* cur1 = headA; struct ListNode* cur2 = headB; //1、判断是否相交 while (cur1->next) { cur1 = cur1->next; lenA++; } while (cur2->next) { cur2 = cur2->next; lenB++; } //若相交，进入if判断 if (cur1 == cur2) { struct ListNode* shortList = headA, * longList = headB; if (lenA > lenB) { longList = headA; shortList = headB; } int num = abs(lenA - lenB); //让长的链表先走差距步 while (num--) { longList = longList->next; } while (shortList && longList) { if (shortList == longList) { return shortList; } //此时两链表一起走 else { shortList = shortList->next; longList = longList->next; }} } //若不相交，则直接返回空 return NULL; }

3、复制带随机指针的链表

链接直达：

复制带随机指针的链表

题目：

文章图片

思路：

法一：直接复制（malloc）+ 找相对距离
定义一个指针cur指向原链表第一个元素，cur指向第一个值为7，再malloc出一个7来，cur往后走，继续malloc，再尾插，以此遍历下去。新的链表复制出来了，关键在于如何处理新链表的random指针，这里可以采用找相对距离的方法，找原链表random指向第几个，那么新链表对应指向第几个。但是这个方法过于复杂，时间复杂度达到了O(N^2)。不是太推荐
法二：
首先，把拷贝节点链接在原节点后面

文章图片

struct Node* cur = head; //1、拷贝节点链接在原节点后面 while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; }

接着，链接拷贝节点的random在原节点random后面
比如我们拷贝出来的13这个数字，拷贝的13的random就是原头13的random的next 。因为在原链表中，13的random指向7，现在想让拷贝出来的13的random指向拷贝出来的7。原链表中，7的next指向拷贝出的7，综上：拷贝的13的random就是原头13的random的next 。以此类推。

文章图片

//2、更新拷贝节点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; }

最后，恢复原链表，把拷贝链表链接在一起

文章图片

//3、拷贝节点剪下来，链接到一起 cur = head; struct Node* copyTail = NULL; struct Node* copyHead = NULL; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; cur->next = next; if (copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } cur = next; } return copyHead; }

总代码如下：

struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; //1、拷贝节点链接在原节点后面 while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; } //2、更新拷贝节点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; } //3、拷贝节点剪下来，链接到一起 cur = head; struct Node* copyTail = NULL; struct Node* copyHead = NULL; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; cur->next = next; if (copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } cur = next; } return copyHead; }