Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 131
Good morning! Here's your coding interview problem for today.

This question was asked by Snapchat.

Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list.

Pull request:
Day131
Resolves #270.

Patch:
diff --git a/README.md b/README.md
index 46a144b..83436b0 100644
--- a/README.md
+++ b/README.md
@@ -137,3 +137,4 @@ problems from
 * [Day 128](https://github.com/vaskoz/dailycodingproblem-go/issues/260)
 * [Day 129](https://github.com/vaskoz/dailycodingproblem-go/issues/263)
 * [Day 130](https://github.com/vaskoz/dailycodingproblem-go/issues/265)
+* [Day 131](https://github.com/vaskoz/dailycodingproblem-go/issues/270)
diff --git a/day131/problem.go b/day131/problem.go
new file mode 100644
index 0000000..3d3d030
--- /dev/null
+++ b/day131/problem.go
@@ -0,0 +1,41 @@
+package day131
+
+// RandomSinglyLL is a singly linked list with a random pointer pointing
+// anywhere in the linked list.
+type RandomSinglyLL struct {
+	Value        int
+	Next, Random *RandomSinglyLL
+}
+
+// DeepCloneRandomSinglyLL deeply clones a RandomSinglyLL.
+// Works in O(N) time and O(1) extra space aside from the O(N) extra space of the result.
+func DeepCloneRandomSinglyLL(head *RandomSinglyLL) *RandomSinglyLL {
+	if head == nil {
+		return nil
+	}
+	original := head
+	for original != nil {
+		clone := &RandomSinglyLL{Value: original.Value, Random: nil, Next: original.Next}
+		original.Next = clone
+		original = original.Next.Next
+	}
+	original = head
+	for original != nil {
+		if original.Random != nil {
+			original.Next.Random = original.Random.Next
+		}
+		original = original.Next.Next
+	}
+	result := head.Next
+	origPtr, copyPtr := head, head.Next
+	for origPtr != nil {
+		origPtr.Next = origPtr.Next.Next
+		if copyPtr.Next == nil {
+			break
+		}
+		origPtr = origPtr.Next
+		copyPtr.Next = copyPtr.Next.Next
+		copyPtr = copyPtr.Next
+	}
+	return result
+}


Test patch:
diff --git a/day131/problem_test.go b/day131/problem_test.go
new file mode 100644
index 0000000..de79aa9
--- /dev/null
+++ b/day131/problem_test.go
@@ -0,0 +1,54 @@
+package day131
+
+import (
+	"testing"
+)
+
+var testcases = []struct {
+	head *RandomSinglyLL
+}{
+	{nil},
+	{&RandomSinglyLL{}},
+	{&RandomSinglyLL{Value: 10, Next: &RandomSinglyLL{Value: 20, Next: &RandomSinglyLL{30, nil, nil}}}},
+	{generateRandomSinglyLL()},
+}
+
+func TestDeepCloneRandomSinglyLL(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := DeepCloneRandomSinglyLL(tc.head); !equalButNotIdentical(tc.head, result) {
+			t.Errorf("DeepClone didn't work for TCID%d", tcid)
+		}
+	}
+}
+
+func BenchmarkDeepCloneRandomSinglyLL(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			DeepCloneRandomSinglyLL(tc.head)
+		}
+	}
+}
+
+func equalButNotIdentical(one, two *RandomSinglyLL) bool {
+	for one != nil && two != nil {
+		if checks(one, two) {
+			return false
+		}
+		one = one.Next
+		two = two.Next
+	}
+	return one == nil && two == nil
+}
+
+func checks(one, two *RandomSinglyLL) bool {
+	return one == two || one.Value != two.Value || (one.Random != nil && one.Random == two.Random) ||
+		(one.Random != nil && two.Random != nil && one.Random.Value != two.Random.Value)
+}
+
+func generateRandomSinglyLL() *RandomSinglyLL {
+	head := &RandomSinglyLL{Value: 10, Next: &RandomSinglyLL{Value: 20, Next: &RandomSinglyLL{30, nil, nil}}}
+	head.Random = head.Next.Next
+	head.Next.Random = head
+	return head
+}