• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

138. 复制带随机指针的链表_链表本地输入运行的问题

开发技术 开发技术 3小时前 2次浏览

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

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

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数

138. 复制带随机指针的链表_链表本地输入运行的问题

例子1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

例子2:

输入:head = []
输出:[]

解释:给定的链表为空(空指针),因此返回null

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':
        Mydic = dict()
        def recursion(node: 'Node'):
            if node is None: return None
            if node in Mydic: return Mydic.get(node)
            root = Node(node.val)
            Mydic[node] = root
            root.next = recursion(node.next)
            root.random = recursion(node.random)
            return root
        return recursion(head)


# 2.1 思路1
# 这个题和剑指offer中的复杂链表的复制是一样的。
# 用一个字典来记录旧链表和新链表各个节点的对应关系。
class SolutionOne(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head == None:
            return None
        memories = {} # 在这个字典里,key是旧链表的节点,val是新链表的节点。
        node = head
        while node != None:
            cloneNode = Node(node.val,None,None)
            memories[node] = cloneNode
            node = node.next
        node = head
        while node:  # 这里用dict.get因为key值如果为空的话,就会返回默认值None
            # 根据字典的映射关系来处理新链表的random和next关系。
            memories.get(node).next = memories.get(node.next)
            memories.get(node).random = memories.get(node.random)
            node = node.next
        return memories[head]   # head的val是head的复制节点(即新节点的头结点)


# 2.2 思路2
# 分三步,第一复制链表,第二复制random关系,
# 第三分离新旧链表。这种做法是在原链表直接复制,空间复杂度为o(1)。
# 注意空节点是没有next节点和random节点的
class SolutionTwo(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head == None:
            return head
        cur = head
        while cur:
            clone = Node(cur.val,cur.next,None)
            curNext = cur.next
            cur.next = clone
            cur = curNext
        cur = head
        while cur:
            if cur.random == None:
                cur.next.random = None
            else:
                cur.next.random = cur.random.next
            cur = cur.next.next
        cur = head
        newHead = head.next
        while cur.next:   # 要是cur.next为空的话,空节点没有next节点,所以循环截止条件就是cur.next为空
            curNext = cur.next
            cur.next = cur.next.next
            cur = curNext
        return newHead


if __name__ == '__main__':
    # headList = [[1,1],[2,1]]
    # headList = [[7,"null"],[13,0],[11,4],[10,2],[1,0]]
    headList = [[3,"null"],[3,0],[3,"null"]]
    # headList = []
    if headList:
        resultList = []
        for i in range(len(headList)):
            node1 = Node(headList[i][0])
            if headList[i][1] == "null":
                pass
            else:
                node2 = Node(headList[i][1])
                node1.next = node2
            result = Solution().copyRandomList(node1)
            # result = SolutionOne().copyRandomList(node1)
            # result = SolutionTwo().copyRandomList(node1)
            nodeList = []
            while (result != None):
                nodeList.append(result.val)
                print(f"索引{i}: ", result.val)
                result = result.next
            if len(nodeList) < 2:
                nodeList.append("null")
            resultList.append(nodeList)
        print("输出: ", resultList)
    else:
        print("输出: ", [])
138. 复制带随机指针的链表_链表本地输入运行的问题138. 复制带随机指针的链表_链表本地输入运行的问题

class SolutionOne(object):
    def copyRandomList(self, head):
        if not head:
            return None
        p = head
        # 第一步,在每个原节点后面创建一个新节点
        # 1->1'->2->2'->3->3'
        while p:
            new_node = Node(p.val,None,None)
            new_node.next = p.next
            p.next = new_node
            p = new_node.next
        p = head
        # 第二步,设置新节点的随机节点
        while p:
            if p.random:
                p.next.random = p.random.next
            p = p.next.next
        # 第三步,将两个链表分离
        p = head
        dummy = Node(-1,None,None)
        cur = dummy
        while p:
            cur.next = p.next
            cur = cur.next
            p.next = cur.next
            p = p.next
        return dummy.next


class SolutionTwo(object):
    def copyRandomList(self, head):
        if not head:
            return None
        # 创建一个哈希表,key是原节点,value是新节点    
        d = dict()
        p = head
        # 将原节点和新节点放入哈希表中
        while p:
            new_node = Node(p.val,None,None)
            d[p] = new_node
            p = p.next
        p = head
        # 遍历原链表,设置新节点的next和random
        while p:
            # p是原节点,d[p]是对应的新节点,p.next是原节点的下一个
            # d[p.next]是原节点下一个对应的新节点
            if p.next:
                d[p].next = d[p.next]
            # p.random是原节点随机指向
            # d[p.random]是原节点随机指向  对应的新节点    
            if p.random:
                d[p].random = d[p.random]
            p = p.next
        # 返回头结点,即原节点对应的value(新节点)
        return d[head]

View Code

c++:

138. 复制带随机指针的链表_链表本地输入运行的问题138. 复制带随机指针的链表_链表本地输入运行的问题

//#include "iostream"
//#include "unordered_map"
//using namespace std;
//
// // Definition for a Node.
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    explicit Node(int _val) {
//        val = _val;
//        next = nullptr;
//        random = nullptr;
//    }
//};
//
//class Solution {
//public:
//    unordered_map<Node*, Node*> cachedNode;
//
//    Node* copyRandomList(Node* head) {
//        if (head == nullptr) {
//            return nullptr;
//        }
//        if (!cachedNode.count(head)) {
//            Node* headNew = new Node(head->val);
//            cachedNode[head] = headNew;
//            headNew->next = copyRandomList(head->next);
//            headNew->random = copyRandomList(head->random);
//        }
//        return cachedNode[head];
//    }
//};
//
//int main() {
//    // 怎么输入?
//}


#include<iostream>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};


void Print(Node* head) {
    Node* cur = head;
    while (cur != NULL) {
        printf("%p(%d)-->  ", cur, cur->val);
        cur = cur->next;
    }
    printf("n");
}

//复制随机链表
Node* CopyRandomList(Node* head)
{
    if (head == NULL) {
        return NULL;
    }
    //创建新节点,插入到旧节点后面
    Node* cur = head;
    while (cur != NULL) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->val = cur->val;
        node->next = cur->next;
        cur->next = node;
        node->random = NULL;
        cur = node->next;
    }
    // 插入成功,复制random指针
    cur = head;
    while (cur != NULL)    {
        if (cur->random != NULL) {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //拆分链表
    cur = head;
    Node* newHead = cur->next;
    while (cur != NULL) {
        Node* nn = cur->next;
        cur->next = nn->next;
        if (nn->next != NULL) {
            nn->next = cur->next->next;
        }
        cur = cur->next;
    }
    return newHead;
}

Node* CreateNode(int val) {
    Node* node1 = (Node*)malloc(sizeof(Node));
    node1->val = val;
    return node1;
}


int main()
{
    Node* node1 = CreateNode(1);
    Node* node2 = CreateNode(2);
    Node* node3 = CreateNode(3);
    Node* node4 = CreateNode(4);
    node1->next = node2; node1->random = node3;
    node2->next = node3; node2->random = node1;
    node3->next = node4; node3->random = node3;
    node4->next = NULL; node4->random = NULL;
    Print(node1);
    Node* newHead = CopyRandomList(node1);
    Print(newHead);
    system("pause");
    return 0;
}

View Code

138. 复制带随机指针的链表_链表本地输入运行的问题

 

 

 c语言:

138. 复制带随机指针的链表_链表本地输入运行的问题138. 复制带随机指针的链表_链表本地输入运行的问题

#include "stdio.h"
#include ".libuthash-mastersrcuthash.h" /* UT_hash_handle */


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

struct HashTable {
    struct Node *key, *val;
    UT_hash_handle hh;
} * cachedNode;

struct Node* deepCopy(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    struct HashTable* tmp;
    HASH_FIND_PTR(cachedNode, &head, tmp);
    if (tmp == NULL) {
        struct Node* headNew = malloc(sizeof(struct Node));
        headNew->val = head->val;
        tmp = malloc(sizeof(struct HashTable));
        tmp->key = head, tmp->val = headNew;
        HASH_ADD_PTR(cachedNode, key, tmp);
        headNew->next = deepCopy(head->next);
        headNew->random = deepCopy(head->random);
    }
    return tmp->val;
}

struct Node* copyRandomList(struct Node* head) {
    cachedNode = NULL;
    return deepCopy(head);
}

int main() {
    // 怎么输入?
}

View Code

java语言:

138. 复制带随机指针的链表_链表本地输入运行的问题138. 复制带随机指针的链表_链表本地输入运行的问题

import java.util.HashMap;
import java.util.Map;

// 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 {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }

    public static void main(String[] args) {
        // 怎么输入??
    }
}

View Code

138. 复制带随机指针的链表_链表本地输入运行的问题138. 复制带随机指针的链表_链表本地输入运行的问题

class SolutionOne {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        Node p = head;
        //第一步,在每个原节点后面创建一个新节点
        //1->1'->2->2'->3->3'
        while(p!=null) {
            Node newNode = new Node(p.val);
            newNode.next = p.next;
            p.next = newNode;
            p = newNode.next;
        }
        p = head;
        //第二步,设置新节点的随机节点
        while(p!=null) {
            if(p.random!=null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        Node dummy = new Node(-1);
        p = head;
        Node cur = dummy;
        //第三步,将两个链表分离
        while(p!=null) {
            cur.next = p.next;
            cur = cur.next;
            p.next = cur.next;
            p = p.next;
        }
        return dummy.next;
    }
}


class SolutionTwo {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        //创建一个哈希表,key是原节点,value是新节点
        Map<Node,Node> map = new HashMap<Node,Node>();
        Node p = head;
        //将原节点和新节点放入哈希表中
        while(p!=null) {
            Node newNode = new Node(p.val);
            map.put(p,newNode);
            p = p.next;
        }
        p = head;
        //遍历原链表,设置新节点的next和random
        while(p!=null) {
            Node newNode = map.get(p);
            //p是原节点,map.get(p)是对应的新节点,p.next是原节点的下一个
            //map.get(p.next)是原节点下一个对应的新节点
            if(p.next!=null) {
                newNode.next = map.get(p.next);
            }
            //p.random是原节点随机指向
            //map.get(p.random)是原节点随机指向  对应的新节点
            if(p.random!=null) {
                newNode.random = map.get(p.random);
            }
            p = p.next;
        }
        //返回头结点,即原节点对应的value(新节点)
        return map.get(head);
    }
}

View Code

 


程序员灯塔
转载请注明原文链接:138. 复制带随机指针的链表_链表本地输入运行的问题
喜欢 (0)