FilesExpand file tree

 master

/

_138.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

50 lines (41 loc) · 1.36 KB

 master

/

_138.java

Top

File metadata and controls

• Code
• Blame

50 lines (41 loc) · 1.36 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

package com.fishercoder.solutions;

import java.util.HashMap;

import java.util.Map;

/**

* 138. Copy List with Random Pointer

*

* A linked list is given such that each node contains an additional random

* pointer which could point to any node in the list or null.

* Return a deep copy of the list.

*/

public class _138 {

public static class Solution1 {

public Node copyRandomList(Node head) {

/**Key is the original nodes, value is the new nodes we're deep copying to.*/

Map<Node, Node> map = new HashMap();

Node node = head;

//loop for the first time: copy the node themselves with only labels

while (node != null) {

map.put(node, new Node(node.val));

node = node.next;

}

//loop for the second time: copy random and next pointers

node = head;

while (node != null) {

map.get(node).next = map.get(node.next);

map.get(node).random = map.get(node.random);

node = node.next;

}

return map.get(head);

}

// Definition for singly-linked list with a random pointer.

class Node {

int val;

Node next;

Node random;

Node(int x) {

this.val = x;

}

}

}

}