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

OJ随机链表的复制题目分析

article 2025/2/28 20:21:13

题目内容：

138. 随机链表的复制 - 力扣（LeetCode）

分析：

这道题目，第一眼感觉非常乱，这是正常的，但是我们经过仔细分析示例明白后，其实也并不是那么难。现在让我们一起来分析分析吧！

1.题目要求的是链表的复制，那么我们得想我们该怎么做，才能很好地进行下去呢？

2.是直接把原链表一个一个地移动过来？这思路果断不对，它还要保持原来的链表不被复制啊.

3.经过观察，我们发现13的random指向7。各种穿插的，所以我们采用

//复制
     struct Node* cur=head;
    while(cur)
    {
      
        
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
         struct Node*Next=cur->next;
        cur->next=copy;
        copy->next=Next;
        cur=Next;

    }

复制部分：

先在每个数复制下来，分别放在它的原数字的下一个。即下图：

4.接着你看它原链表的那些数字。7的random指向NULL，13的random指向7.（其他的省略说）。7的next指向13。看到这种规律，我们试想是不是可以把复制的也弄成这样子，就形成了一个独立的复制链表了，对吧？

连线部分：

 //连接线
   cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
       // struct Node* Next=cur->next->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;

        }
        cur=cur->next->next;
        
    }

如下图：

你看复制完了之后，是不是可以直接它复制那部分挪下来，它也是不会破坏原链表的，这是不是就符合题目要求了对吧？

5.完成了这步了之后，到了我们一个一个挪的那部分了。

如下图：

解释上图：

 //复制的挪下来，恢复原链表
    
    
    
    struct Node* copyhead=NULL,*copytail=NULL;
    cur=head; 
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* Next=copy->next; 
        //尾插
        if(copyhead==NULL)
        {
            copyhead=copytail=copy;
        }
        else
        {
            copytail->next=copy;
            copytail=copytail->next;
            
        }

挪动部分：

当我们复制完了之后，开始挪新的复制链表：

1.首先定义一个cur指针指向head头。再定义一个next指针指向cur的下一个（方便它随时都能返回找到copy的位置）。

2.定义两个指针分别为copyhead和copytail指针，放在新的链表那里当作移动工具和最后返回工具

2.接着，相当于进行尾插，当第一次时，copyhead和copytail都为空时，就把copy值直接放到这个指针

3.不为空时，就把copy值放到copytail的下一位。

恢复部分：

最后，恢复原来的链表，即去掉它copy的那些数：

1.因为我们上面都没有动过cur的位置，所以这里就直接使用cur这个指针就行了。

2.把cur的下一个给Next即：把cur的下一个next给给cur的next的next（即cur的下下个）。

  //恢复链表
            cur->next=Next;
            cur=Next;

总代码：

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

struct Node* copyRandomList(struct Node* head) {
	//复制
     struct Node* cur=head;
    while(cur)
    {
      
        
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
         struct Node*Next=cur->next;
        cur->next=copy;
        copy->next=Next;
        cur=Next;

    }
    //连接线
   cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
       // struct Node* Next=cur->next->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;

        }
        cur=cur->next->next;
        
    }
    //复制的挪下来，恢复原链表
    
    
    
    struct Node* copyhead=NULL,*copytail=NULL;
    cur=head; 
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* Next=copy->next; 
        //尾插
        if(copyhead==NULL)
        {
            copyhead=copytail=copy;
        }
        else
        {
            copytail->next=copy;
            copytail=copytail->next;
            
        }
        //恢复链表
            cur->next=Next;
            cur=Next; 
    
    }
    return copyhead;
}

最后，特别要注意的是：cur的位置要每到一部分都要及时更新变成head。（因为它每一部分都在改变），不然就会像我一开始那样，发现怎么都不正确哇哇哇哇。