当前位置：首页 > article >正文

【初阶数据结构篇】单链表OJ题（下篇）

article 2024/11/24 22:20:07

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

接上篇：【初阶数据结构篇】单链表OJ题（上篇）-CSDN博客

8. 相交链表

题目链接：160. 相交链表 - 力扣（LeetCode）

题目描述：

补充：

思路1：相对简单，易理解

。先分别求出两个链表的长度，让相对更长的链表走到与小链表长度相同的位置

。再循环对该链表进行判断是否存在相交链表，存在则返回true，不存在返回false

注意：里面的细节处理很重要。

8.1 示例代码：

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
    {
        return NULL;
    }
    ListNode* lessHead=headA;
    ListNode* greathead=headB;
    int count1=0,count2=0;
    while(lessHead)
    {
        count1++;
        lessHead=lessHead->next;
    }
     while(greathead)
    {
        count2++;
        greathead=greathead->next;
    }
    if(count1>count2)
    {
        lessHead=headB;
        greathead=headA;
        while(count1-count2>0)
        {
        greathead=greathead->next;
        count1--;
        }
    }
    else{
        lessHead=headA;
        greathead=headB;
        while(count2-count1>0)
        {
        greathead=greathead->next;
        count2--;
        }
    }
    while(lessHead&&greathead)
    {
        if(lessHead==greathead)
        {
            return lessHead;
        }
        lessHead=lessHead->next;
        greathead=greathead->next;
    }
    return NULL;
}

思路2：

让两个链表同时先后走，当其中任何一个链表走到空，将该链表重新置为另一个链表的头，继续往后走，（另一个链表与之相同）直至相遇，返回相遇的节点即可。

为啥正确？？？

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

9. 环形链表

题目链接：141. 环形链表 - 力扣（LeetCode）

题目描述：

思路：经典快慢指针算法

9.1 示例代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            return true;
        }
        return false;
    }
};

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

空间复杂度：O(1)。

10.环形链表 ||

题目链接：

142. 环形链表 II - 力扣（LeetCode）

题目描述：

思路：找链表的相交节点，再将链表的相交节点与头结点同时走，相遇时就是相交链表的入口节点。

正确性

10.1 示例代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //快慢指针找相遇点
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            //存在环
            if(slow==fast)//相遇点
            {
                 ListNode* pcur=head;
                while(slow!=pcur)
                {
                    slow=slow->next;
                    pcur=pcur->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

11.随机链表的复制

题目链接:138. 随机链表的复制 - 力扣（LeetCode）

题目描述：

补充：

思路：在原链表基础上进行复制链表，置random指针，将复制链表与原链表断开。

11.1 示例代码：

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);
        pcur->next=newnode;
        newnode->next=Next;

        pcur=Next;
    }
 }
struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return NULL;
    }
	//原链表上复制节点
    AddNode(head);
    //置random指针
    Node* pcur=head;
    while(pcur)
    {
        Node* copy=pcur->next;
        if(pcur->random!=NULL)
        {
            copy->random=pcur->random->next;
        }
        pcur=copy->next;
    }
    //将复制链表与原链表断开
    pcur=head;
    Node* newhead,*newTail;
    newhead=newTail=pcur->next;
    while(pcur->next->next)
    {
        pcur=pcur->next->next;
        newTail->next=pcur->next;
        newTail=newTail->next;
    }
    return newhead;
}