题解 | #复杂链表的复制#

复杂链表的复制

http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba

最笨最直接的方法:

  1. 根据next指针将链表的label值拷贝出来生成新的链表pNode。
  2. 两个链表同时遍历,填充random
  • 每一个元素,内部再两个链表同时遍历
  • 找到第一个的random时,第二个链表也指向正确的random,此时赋值给第二个的random
  • 注意几个特殊情况:random指向空,random指向自己

本方法的时间复杂度O(n+n^2) = O(n^2);空间复杂度O(1)

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        RandomListNode* p1 = pHead;
        // for label and next
        RandomListNode* pNode = new RandomListNode(p1->label);
        RandomListNode* p2 = pNode;
        while(1){
            if(p1->next == nullptr){
                p2->next = nullptr;
                break;
            }
            RandomListNode* pNew = new RandomListNode(p1->next->label);
            p2->next = pNew;
            p1 = p1->next;
            p2 = p2->next;
        }
        // for random
        p2 = pNode;
        p1 = pHead;
        while(p2){//p2 loop
            if(!p1->random){
                p2->random=nullptr;
                p2 = p2->next;
                p1 = p1->next;
                continue;
            }
            if(p1->random == p1){
                p2->random=p2;
                p2 = p2->next;
                p1 = p1->next;
                continue;
            } 
            
            RandomListNode* cursor1 = pHead;
            RandomListNode* cursor2 = pNode;
            while(cursor1){
                if(p1->random == cursor1){
                    p2->random = cursor2;
                    break;
                }
                cursor1 = cursor1->next;
                cursor2 = cursor2->next;
            }
            p2 = p2->next;
            p1 = p1->next;
        }
        return pNode;
    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务