链表相关oj题 三

目录

 

一、环形链表II

思路一：

 思路二：

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

---

 

一、环形链表II
 

142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)
题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。

如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

如果 pos 是 -1，则在该链表中没有环。

注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路一：

图解：

 代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
    //1.找到slow和fast的相遇点
    //2.head从头指针处每次走一步,MeetNode每次走一步
    //他们会在入环的第一个节点处相遇
    struct ListNode* cur = head;
    struct ListNode* slow = head;
    struct ListNode* fast= head;
    struct ListNode* MeetNode = NULL;
    while(fast && fast->next)//无环的情况
    {   
        //过程中所遇到的问题1：

        //没有相遇
        // if(slow != fast)//slow头指针处 == fast , err
        // {
        //     slow = slow->next;
        //     fast = fast->next->next;
        // }

           slow = slow->next;
           fast = fast->next->next;
        //相遇的情况
        if(slow == fast)
        {
            MeetNode = slow;
            while(MeetNode != head)
            {
               MeetNode = MeetNode->next;
               head = head->next;
            }
            return MeetNode;
        }
    }
    return NULL;
}

运行结果：

 思路二：

图解：

 代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
    //1.找到fast和slow的相遇点,
    //2.将MeetNode的下一个节点作为另一个链表的头
    //3.然后计算俩个头指针到达MeetNode节点的距离
    //4.变为相同长度的链表，然后向后依次比较是否为同一个节点
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* MeetNode = NULL;
    struct ListNode* list = NULL;
    struct ListNode* list1 = NULL;
    struct ListNode* head1 = NULL;
    //是否为不为环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                MeetNode = slow;
                list = MeetNode->next;
                list1 = list;
                head1 = head;
                int lengthA = 1;
                //判断俩个链表到达MeetNode的长度
                while(list != MeetNode)
                {
                    ++lengthA;
                    list = list->next;
                }
                int lengthB = 1;
                while(head != MeetNode)
                {
                    ++lengthA;
                    head = head->next;
                }
                int length = abs(lengthA - lengthB);
                struct ListNode* LongList = list1;
                struct ListNode* ShortList = head1;
                if(lengthA < lengthB)
                {
                    LongList = head1;
                    ShortList = list1;
                }
                while(length--)
                {
                    LongList = LongList->next;
                }
                //进行判断是否为同一个节点
                while(LongList != ShortList)
                {
                    LongList = LongList->next;
                    ShortList = ShortList->next;
                }
                return LongList;       
        }
    }
     return NULL;
}

运行结果：

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

138. 复制带随机指针的链表 - 力扣（LeetCode） (leetcode-cn.com)

题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。

 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。

复制链表中的指针都不应指向原链表中的节点 。

图解：

代码：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) 
{
    //1.复制节点：将新建节点插入到原节点和原节点下一个位置之间
    struct Node* cur = head;
    while(cur)
    {
        //创建新节点,是每一个独立的新节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //将原节点中的值放入新节点中
        copy->val = cur->val;
        //插入copy节点
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    
    //2.根据原节点：处理copy节点的random

    cur = head;
    while(cur)
    {
        //创建一个共同的指针，指向每一个新节点
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    
    //3.将复制节点解下来，链接成一个新的链表，恢复原链表链接关系
    cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur)
    {
        //进行copy和Next的迭代
        struct Node* copy = cur->next;
        struct Node* Next = copy->next;
        //没有头结点，所以要进行头指针判空
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        //如果不是NULL，那么就将copy所指向的节点放在copytail后面
        else
        {
            copytail->next = copy;
            //将copytail再指向下一个节点，也就是新建链表的尾结点
            copytail = copy;
        }
        //进行原节点的还原
        cur->next = Next;
        //将cur指向下一个原节点
        cur = Next;
    }
    //最后因为copy原来的next就是为NULL，所以cur为NULL，出来时，新链表不用处理，最后是否指向NULL的情况，因为最后指向的就是NULL
    //返回copy链表的头指针
    return copyhead;   
}

运行结果：

 本篇为链表oj题的相关内容，如有问题，请评论区多多评论^_^