【刷算法】复杂链表的复制

Mike617 发布于2019-08-22 18:32 / 1617人阅读

摘要：题目描述输入一个复杂链表每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点，返回结果为复制后复杂链表的。

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

分析

常规的复制链表只需要考虑每个节点的next指针即可，但是该题还有另外一个random指针，且没有规律，可能指向任何其他节点，此时需要解决的问题是如何复制random指针。开始想先通过next指针构建新的链表，同时使用栈保存各个新节点，然后再通过栈来构建random指针，但是发现过程中并没有这么简单，比如对于A.random=C来说，那么在新链表中就是A1.random=C1，我无法在新链表中以O(1)的时间复杂度访问C1，所以我这种方法受阻。

在网上查到一种思路，遍历链表的时候把每个新节点添加在旧节点的后面，比如 A->B->C，复制完是A->A1->B->B1->C->C1，然后对于每个复制节点来说来说，A1.random=A.random.next，B1.random=B.random.next，C1.random=C.random.next，完美的解决了复制random指针时获取到目标节点的问题。最后再拆成两条链表即可。

代码实现

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/
function Clone(h)
{
    if(h === null)
        return h;
    var cur = h;
    // 第一次遍历，先复制所有节点，且把复制节点添加到相应节点后面
    while(cur !== null) {
        var node = new RandomListNode(cur.label);
        node.next = cur.next;
        cur.next = node;
        cur = node.next;
    }
    
    cur = h;
    // 第二次遍历，复制random指针
    while(cur !== null) {
        if(cur.random !== null){
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }
    var clonedH = h.next;
    var temp;
    cur = h;
    // 第三次遍历，把链表拆开
    while(cur.next !== null) {
        temp = cur.next;
        
        cur.next = cur.next.next;
        cur = temp;
    }   
    
    return clonedH;
}

私有云 GPU服务器 linux链表的安全访问合并链表的c语言学生链表的c语言代码关于链表的c语言代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95978.html

Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0
【刷算法】LeetCode.19-删除链表的倒数第N个节点

摘要：题目描述给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。题目描述给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：给定的 n 保证是有效...

Binguner 2019-08-23 11:37 评论0 收藏0
＜LeetCode天梯＞Day025 删除链表的倒数第N个节点（双指针） | 初级算法 | Pyth

摘要：示例输入输出示例输入输出示例输入输出提示双指针法分析根据题干的要求，我们需要删除倒数第个节点，在返回头结点。只需要找到倒数第个节点，将其删除，再返回。 ?作者简...

andot 2021-11-16 11:45 评论0 收藏0