FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode/CopyListWIthRandomPointer.java at master · Orio77/LeetCode · GitHub

119 lines (96 loc) · 2.63 KB

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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

// Definition for a Node.

import java.util.HashMap;

import java.util.Map;

class Node {

int val;

Node next;

Node random;

public Node(int val) {

this.val = val;

this.next = null;

this.random = null;

}

}

class MySolution {

public Node copyRandomList(Node head) {

if (head == null) {

return null;

}

Node dummy = head;

Node copyHead = getNode(head);

Node copyDummy = copyHead;

while (dummy.next != null) {

copyDummy.next = getNode(dummy.next);

dummy = dummy.next;

copyDummy = copyDummy.next;

}

return copyHead;

}

public Node getNode(Node original) {

Node copied = new Node(original.val);

copied.next = original.next;

copied.random = original.random;

return copied;

}

}

class MySolution2 {

public Node copyRandomList(Node head) {

return getNode(head);

}

public Node getNode(Node original) {

if (original == null) {

return null;

}

if (original.next == null) {

Node copied = new Node(original.val);

copied.next = null;

copied.random = getNode(original.random);

}

if (original.random == null) {

Node copied = new Node(original.val);

copied.next = getNode(original.next);

copied.random = null;

return copied;

}

Node copied = new Node(original.val);

copied.next = getNode(original.next);

copied.random = getNode(original.random);

return copied;

}

}

class MySolution3 {

public Node copyRandomList(Node head) {

if (head == null) {

return null;

}

Node dummy = head;

Node copyHead = new Node(head.val);

Node copyDummy = copyHead;

while (dummy.next != null) {

copyDummy.next = new Node(dummy.next.val);

dummy = dummy.next;

copyDummy = copyDummy.next;

}

dummy = head;

copyDummy = copyHead;

return copyHead;

}

}

class Solution {

public Node copyRandomList(Node head) {

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

Node cur = head;

while (cur != null) {

oldToCopy.put(cur, new Node(cur.val));

cur = cur.next;

}

cur = head;

while (cur != null) {

Node copy = oldToCopy.get(cur);

copy.next = oldToCopy.get(cur.next);

copy.random = oldToCopy.get(cur.random);

cur = cur.next;

}

return oldToCopy.get(head);

}

}

Back | FazBrowse Home | New Git URL