网站导航
> 技术文档 > 【数据结构】LeetCode160.相交链表 138.随即链表复制 牛客——链表回文问题

【数据结构】LeetCode160.相交链表 138.随即链表复制 牛客——链表回文问题

网友: 技术文档 2025-09-02 19:11:20

文章目录

    • 一、相交链表问题
      • 问题描述
      • 解题思路分析
        • 思路一：暴力遍历法
        • 思路二：双指针对齐法（最优解）
    • 二、链表的回文结构
      • 问题描述
      • 解题思路
      • 完整代码
    • 三、 随即链表的复制
      • 问题描述
      • 解题思路
      • 复杂度分析

一、相交链表问题

问题描述

给定两个单链表，判断它们是否相交，若相交则返回相交的节点。（注意：判断依据是节点地址是否相同，而非节点值，因为节点值可能存在重复。）

在这里插入图片描述

解题思路分析

思路一：暴力遍历法
  • 方法：遍历链表A，对于A中的每一个节点，遍历整个链表B，检查是否存在地址相同的节点。
  • 时间复杂度：O(M*N)（若两链表长度分别为M和N）
  • 空间复杂度：O(1)
  • 缺点：效率低，不适用于长链表。
思路二：双指针对齐法（最优解）
  • 方法：
    1. 分别遍历两个链表，计算各自长度。
    2. 求出两链表长度差 gap。
    3. 让较长的链表的指针先移动 gap 步。
    4. 然后两个指针同时移动，逐个比较节点地址，第一个相同的节点即为交点。
  • 时间复杂度：O(M + N)
  • 空间复杂度：O(1)
  • 优点：高效，适用于任意长度的链表。

在这里插入图片描述

思路2的时间复杂度更低，所以我们选择思路2

具体代码如下

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* 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长 struct ListNode* longList=headA; struct ListNode* 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; } return NULL;}

二、链表的回文结构

问题描述

判断一个单链表是否为回文结构。即正着读和反着读都一样

在这里插入图片描述

解题思路

回文链表判断的关键在于对称性验证。我们可以通过以下步骤实现：

  1. 找到中间节点：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针正好在中间。
  2. 反转后半部分链表：从中间节点开始，将后半部分链表反转。
  3. 比较前后两部分：从头节点和反转后的中间节点开始，逐个比较节点值是否相同。

完整代码

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;}};

三、 随即链表的复制

问题描述

实现一个函数，复制一个含有随机指针的链表。随机指针可以指向链表中的任何节点或为空。

在这里插入图片描述

解题思路

常规链表的复制很简单，但随机指针的存在使得问题复杂化。因为随机指针可能指向尚未复制的节点。我们可以通过以下三步解决：

  1. 插入拷贝节点：在原链表的每个节点后插入一个拷贝节点，值与原节点相同。
  2. 设置随机指针：拷贝节点的随机指针应指向原节点随机指针所指节点的下一个节点（即其拷贝）。
  3. 分离链表：将混合链表分离为原链表和拷贝链表。

在这里插入图片描述

struct Node* copyRandomList(struct Node* head) {//拷贝节点插到原节点后边struct Node*cur=head;while(cur){ struct Node* copy=(struct Node*)malloc(sizeof(struct Node));//分配内存 copy->next=cur->next; cur->next=copy; copy->val=cur->val; cur=copy->next;//cur走到原链表的下一个 }//控制randomcur=head;while(cur){ struct Node* copy = cur->next; if(cur->random==NULL)//不要写成random==NULL { copy->random=NULL; } else { copy->random=cur->random->next;//核心代码 } cur=copy->next;}//把拷贝链表尾插起来struct Node* copyhead=NULL,*copytail=NULL; cur=head;while(cur){ struct Node*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)，除了返回的拷贝链表外，仅使用了常数个额外指针。
网络标签：

相关问题