【数据结构】LeetCode160.相交链表 138.随即链表复制 牛客——链表回文问题
文章目录
一、相交链表问题
问题描述
给定两个单链表，判断它们是否相交，若相交则返回相交的节点。（注意：判断依据是节点地址是否相同，而非节点值，因为节点值可能存在重复。）
解题思路分析
思路一：暴力遍历法
- 方法：遍历链表A，对于A中的每一个节点，遍历整个链表B，检查是否存在地址相同的节点。
- 时间复杂度：O(M*N)（若两链表长度分别为M和N）
- 空间复杂度：O(1)
- 缺点：效率低，不适用于长链表。
思路二：双指针对齐法（最优解）
- 方法：
- 分别遍历两个链表，计算各自长度。
- 求出两链表长度差
gap。 - 让较长的链表的指针先移动
gap步。 - 然后两个指针同时移动，逐个比较节点地址，第一个相同的节点即为交点。
- 时间复杂度：O(M + N)
- 空间复杂度：O(1)
- 优点：高效，适用于任意长度的链表。
思路2的时间复杂度更低，所以我们选择思路2
具体代码如下
structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){ curA=curA->next; lenA++;}while(curB->next){ curB=curB->next; lenB++;}int gap=abs(lenA-lenB);//假设法 先假设A长structListNode* longList=headA;structListNode* shortList=headB;if(lenA<lenB){ longList=headB; shortList=headA;}while(gap--){ longList=longList->next;}while(longList){if(longList==shortList)return longList; longList=longList->next; shortList=shortList->next;}returnNULL;}二、链表的回文结构
问题描述
判断一个单链表是否为回文结构。即正着读和反着读都一样
解题思路
回文链表判断的关键在于对称性验证。我们可以通过以下步骤实现：
- 找到中间节点：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针正好在中间。
- 反转后半部分链表：从中间节点开始，将后半部分链表反转。
- 比较前后两部分：从头节点和反转后的中间节点开始，逐个比较节点值是否相同。
完整代码
class PalindromeList { public: //寻找中间节点 struct ListNode* middleNode(struct ListNode* head) { // 初始化快慢指针 struct ListNode* slow = head; struct ListNode* fast = head; // 移动指针直到fast到达链表末尾 while (fast != NULL && fast->next != NULL) { slow = slow->next; // 慢指针每次移动一步 fast = fast->next->next; // 快指针每次移动两步 } return slow; // 慢指针指向中间节点 } //反转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1, *n2, *n3; n1 = NULL; n2 = head; if (n2) 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 struct ListNode*mid=middleNode(A); struct ListNode*rmid=reverseList(mid); while(rmid&&A) { if(rmid->val!=A->val) return false; rmid=rmid->next; A=A->next; } return true; } }; 三、 随即链表的复制
问题描述
实现一个函数，复制一个含有随机指针的链表。随机指针可以指向链表中的任何节点或为空。
解题思路
常规链表的复制很简单，但随机指针的存在使得问题复杂化。因为随机指针可能指向尚未复制的节点。我们可以通过以下三步解决：
- 插入拷贝节点：在原链表的每个节点后插入一个拷贝节点，值与原节点相同。
- 设置随机指针：拷贝节点的随机指针应指向原节点随机指针所指节点的下一个节点（即其拷贝）。
- 分离链表：将混合链表分离为原链表和拷贝链表。
structNode*copyRandomList(structNode* head){//拷贝节点插到原节点后边structNode*cur=head;while(cur){structNode* copy=(structNode*)malloc(sizeof(structNode));//分配内存 copy->next=cur->next; cur->next=copy; copy->val=cur->val; cur=copy->next;//cur走到原链表的下一个 }//控制random cur=head;while(cur){structNode* copy = cur->next;if(cur->random==NULL)//不要写成random==NULL{ copy->random=NULL;}else{ copy->random=cur->random->next;//核心代码} cur=copy->next;}//把拷贝链表尾插起来structNode* copyhead=NULL,*copytail=NULL; cur=head;while(cur){structNode*copy=cur->next;if(copytail==NULL){ copyhead=copytail=copy;}else{ copytail->next=copy; copytail=copytail->next;} cur=copy->next;}return copyhead;}复杂度分析
- 时间复杂度：O(N)，三次遍历链表。
- 空间复杂度：O(1)，除了返回的拷贝链表外，仅使用了常数个额外指针。
