精华内容
下载资源
问答
  • 复制链表

    2011-09-13 22:52:07
    题目:已知一链表,每个节点...这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样...

    题目:已知一链表,每个节点除了有一个指向下一节点的指针外,还有一随机指针指向链表中的任意节点(可能为空,也有可能为自身),请复制一个链表,要求节点的顺序以及节点上的随机指针指向的节点位置和原链表一致。

     

     

     

    这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样。

     

     

    typedef struct Node {
        int nData;
        Node* pNext;
        Node* pRandom;
    } Node;
    
    Node* DuplicateList(Node* pSrcListHead)
    {
        if (pSrcListHead == NULL)
            return NULL;
     
        Node* pNode = pSrcListHead;
        while (pNode != NULL)
        {
            Node* pNewNode = new Node;
            pNewNode->nData = pNode->nData;
            pNewNode->pNext = pNode->pNext;
            pNewNode->pRandom = pNode->pRandom;
    
            pNode->pNext = pNewNode;
            pNode = pNewNode->pNext;
        }
     
        Node* pDestListHead = pSrcListHead->pNext;
    
        pNode = pSrcListHead;
        while (pNode != NULL)
        {
            pNode->pNext->pRandom = pNode->pRandom->pNext;
            pNode = pNode->pNext->pNext;
        }
    
        pNode = pSrcListHead;
        Node* pNode2 = pNode->pNext;
        while (pNode != NULL)
        {
            pNode->pNext = pNode2->pNext;
            pNode = pNode->pNext;
    
            if (pNode)
                pNode2->pNext = pNode->pNext;
            else
                pNode2->pNext = NULL;
    
            pNode2 = pNode2->pNext;
        }
    
        return pDestListHead;
    }

     

        不过目前还未考虑到原始链表有环的情况,如果原始链表有环,则应该先求出环的入口点,然后利用上面的方法进行链表复制。

     

     

    原文地址:http://hi.baidu.com/%B3%A3%D1%C5%C3%F4/blog/item/173d50ae523a0ede7dd92a63.html

    展开全文
  • 题目 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next ...第三步,将链表剥离,恢复原链表,并产生复制链表。 代码 /* // Definition for a Node. class Node { int val; No

    题目

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

    思路

    第一步,将1-2-3链表变成1-1-2-2-3-3,每个节点都复制一个其克隆节点。
    第二步,将复制的克隆节点的random赋值。
    第三步,将链表剥离,恢复原链表,并产生复制链表。

    代码

    /*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null){
                return null;
            }
            Node cur = head;
            Node pre =new Node(-1);
            //复制节点,1-2-3变为1-1-2-2-3-3
            while(cur != null){
                //深拷贝需要创建新节点
                Node node =new Node(cur.val);
                node.next = cur.next;
                cur.next = node;
                cur = node.next;
            }
            cur = head;
            //处理克隆节点的random
            while(cur!= null){
                 if (cur.random != null){
                     cur.next.random = cur.random.next;
                 }
                cur = cur.next.next;
            }
            
            
            cur = head.next;
            //保存复制链表的头节点
            Node cloneHead = head.next;
            Node now = head;
            //将链表分离,恢复原始链表,并剥离出新复制链表
            while(cur.next != null){
                now.next = now.next.next;
                cur.next = cur.next.next;
                cur = cur.next;
                now = now.next;
            }
            // 单独处理原链表尾节点
            now.next = null; 
            return cloneHead;
        }
    }
    
    展开全文
  • import java.util.*; //复制复制链表 public class P2 { public static class Node{ int val; Node next; Node random; } //复制复制链表方法、一 static Node copy(Node head){ ...
    import java.util.*;
    
    //复制复制链表
    public class P2 {
        public static class Node{
            int val;
            Node next;
            Node random;
        }
        //复制复制链表方法、一
        static Node copy(Node head){
            Node p=head;
            while(p!=null){
                Node q=new Node();
                q.val=p.val;
                q.next=p.next;  // 把q插到p的后边
                p.next=q;
                p=q.next;
            }
            p=head;
            while(p!=null){
                Node q=p.next;
                if(p.random!=null){
                    q.random=p.random.next;
                }else{
                    q.random=null;
                }
                p=q.next;
            }
            //第三步把两个链表拆开 省略
            return head;
        }
        //复制复制链表方法二
        Node copy2(Node head){
            Node p=head;
            Node result=null;
            Node last=null;
            Map<Node,Node> map=new HashMap<>();
            while(p!=null){
                Node q=new Node();
                q.val=p.val;
                if(result==null){
                    result=q;
                }else{
                    last.next=q;
                }
                last=q;
                map.put(p,q);
                p=q.next;
            }
            p=head;
            Node q=result;
            while(p!=null){
                q.random=map.get(p.random);
                p=p.next;
            }
            return result;
        }
    }
    

     

    展开全文
  • 题目描述 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random ...第二步:设置复制链表上的 m_psibling 。如果原始链表节点N的 m_psibling 指

    题目描述

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
    来源:力扣(LeetCode)

    在这里插入图片描述
    在这里插入图片描述

    解题思路

    剑指书上的方法

    1.方法一
    • 第一步:复制原始链表上的每个节点N、创造N’ ; 把创造出来的节点用 m_pnext链接起来; 把<N,N’>放进哈希表。
    • 第二步:设置复制链表上m_psibling 。如果原始链表节点N的 m_psibling 指向节点S; 复制链表当中的 N’ 指向 S’ 。
    2.方法二
    • 第一步:复制链表的节点,将复制的节点接到原始节点的后面
      e.g. 1 -> 1’ -> 2 -> 2’ -> 3 -> 3’
    • 第二步:将链表复制节点的 random 指向的指针 (n.next.random),指向原始节点的后面 (n.random.next)

    Leetcode上的方法

    • 题意的复制是指『深拷贝』(Deep Copy)<=> 浅拷贝(Shallow Copy)
      • 浅拷贝只复制了某个对象的指针,而不复制对象本身,共享同一块内存。 => newhead = head (这只是将指针指到了 head)
      • 深拷贝要创造一个一模一样的对象,新对象跟旧对象不共享内存,修改新对象不会改到原对象。

    source: Leetcode

    • 用 DFS(Depth-First Search)的递归解法
      • 将已经存在的节点存入 Hash Table。
      • 从最深的一个节点开始复制。
      • 在写逻辑的时候,思考最后一步的要件(判断逻辑 & 返回),递归解法都是如此操作。

    Python代码

    """
    # Definition for a Node.
    class Node:
        def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
            self.val = int(x)
            self.next = next
            self.random = random
    """
    class Solution:
        def copyRandomList(self, head: 'Node') -> 'Node':
            """
            剑指方法二
            """
    
            if not head:
                return None
            n = head
            # next指针:1->1'->2->2'->3->3'
            while n:
                node = Node(n.val)
                node.next = n.next
                n.next = node
                n = node.next
           
            # random指针
            n = head
            while n:
                if not n.random:
                    n.next.random = None
                else:
                    n.next.random = n.random.next # 这边是回到原始n链表的随机的下一个复制的点
                n = n.next.next
    
            # 跨号返回
            n = head.next
            while n.next:
                n.next = n.next.next
                n = n.next
            return head.next
    		
    		
    		"""
    		Leetcode方法:用DFS解
    		"""
            def dfs(head):
                if not head:
                    return None
                if head in visited:
                    return visited[head] 
                
                # Deep Copy:创建复制的新节点
                copy = Node(head.val)
                visited[head] = copy
                copy.next = dfs(head.next)
                copy.random = dfs(head.random)
                return copy
            visited = {}
            return dfs(head)
    
    
    展开全文
  • 复制链表的复制

    2017-08-05 23:03:39
    题目:/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {...*/输入一个复杂链表(每个节点中有节点值,以及两个指针,
  • 链表面试题复制链表

    2019-09-08 17:12:53
    给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 分析: 在这里介绍两种解法: 1.指利用链表 2.利用Map集合 1>利用链表 public class Practice2 ...
  • 什么是复杂链表?复杂链表指的是一个链表...今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。复杂链表的数据结构如下:1 typedef int DataType; //数据域的类型23 //复杂链表的数据结构45 typede...
  • //第二个函数,复制链表,要用到L链表的第一位,怎么访问? # include # include typedef struct Node { char data; struct Node *next; }Node,*Linklist; Linklist Createfromtail()//尾插法建立链表 { ...
  • 目录题目描述时间限制本题知识点题目详细...输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请...
  • 我要复制一个链表_ void list_piece(const node* start_ptr, const node* end_ptr, node*& head_ptr, node*& tail_ptr) start_ptr 和end_ptr 不是NULL head_ptr tail_ptr 是新链表的头指针和尾指针,...
  • System.out.println("\n复制链表(value+5):\n按next指针排序:"); Node result=clone(node1); temp=result; while(temp!=null) { System.out.print(temp.value+"\t"); temp=temp.next; ...
  • 第四十六题 复制链表

    2014-06-27 20:15:00
    方法:在不借助辅助空间基础上,我们考虑通过在原始链表中对每个节点A创建对应的A*,将A*链接在A的后面,这样就将值和下一个节点指针复制好了,现在就需要复制随机节点了 #include using namespace std; struct ...
  • 链表结点复制的时候需要申请动态内存,且不同结点申请不同大小的内存
  • 初阶:复制一个简单链表。假设链表节点只包含data和next。 进阶:假设链表节点新增一个属性叫random,他随机指向了链表中的任何一个节点。复制这个链表
  • 链表复制

    2019-09-30 14:38:32
    题目:已知一链表,每个...这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样。 ...
  • 1.本题知识点    链表,复杂问题分解,复制 2. 题目描述   输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个...   ① 复制链表中的每一个节点    ② 原链表中A指向C,那么新复制的节...
  • 复杂链表复制

    2019-07-29 10:05:13
    复杂链表就是指既有next(指向下一个节点的指针),又有random(随机指针),对于普通的只有一个next的链表,复制的时候只需要新建一个节点复制其val,再用尾插的原理就可以复制链表,而对于复杂链表,不仅要考虑next...
  • 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 解题思路 1.拷贝原链表的每一个...
  • 复杂链表复制

    2018-07-24 16:41:23
    剑指offer第25题: 输入一个复杂链表(每个节点中有节点值,以及两个...本题是一个复制链表的题。看似比较复杂,其实原理还是非常简单的。一共有两类指针,一类是指向下一个,一类是指向任意一个。新建一个Rand...
  • 题目: 在复杂链表中,每个节点除了一个next引用外还有一个random引用指向链表中的任意结点或者null,实现函数复制该链表。...第二步:(第二次遍历原链表)设置复制链表上的每个random结点; 总的时间复杂度为O(N)
  • 链表复制算法

    千次阅读 2012-07-18 20:26:57
    已知一个简单链表,请复制链表并返回头结点指针。 解法1:遍历算法 从头开始遍历原链表,依次复制链表各个节点。 结点定义如下: struct node { int data; struct node* next; }; typedef struct node...
  • 思路1 :最简单的思路就是直接复制以next为一链的链表,在之后遍历原链表获取random的链表值,在复制链表上去从头到尾的寻找对应的random值。 举例:原链表的节点 A ,在复制链表上节点为 A’ ,A的random指向C,...
  • 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如,如果原链表中有 X 和 Y 两个节点,...
  • 复杂链表复制 链表判环 无环单链表判相交 复杂链表复制输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)我的提交# -*- coding:utf-8 -*- # class ...
  • 复制复杂链表

    千次阅读 2016-06-25 00:58:44
    什么是复杂链表??? ... 如图,这是一个复杂...复制复杂链表!!! 实现这个问题的方法比较多,下面来介绍三种方法。。 方法一:  新建一个头结点,先不考虑Sibling,将整个单链表复制一份。然后寻

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 133,531
精华内容 53,412
关键字:

复制链表