Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 208
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

Given a linked list of numbers and a pivot `k`, partition the linked list so that all nodes less than `k` come before nodes greater than or equal to `k`.

For example, given the linked list `5 -> 1 -> 8 -> 0 -> 3` and `k = 3`, the solution could be `1 -> 0 -> 5 -> 8 -> 3`.

Pull request:
Day208
Resolves #427.

Patch:
diff --git a/README.md b/README.md
index 6635748..1fc5241 100644
--- a/README.md
+++ b/README.md
@@ -216,3 +216,4 @@ problems from
 * [Day 203](https://github.com/vaskoz/dailycodingproblem-go/issues/419)
 * [Day 204](https://github.com/vaskoz/dailycodingproblem-go/issues/421)
 * [Day 206](https://github.com/vaskoz/dailycodingproblem-go/issues/424)
+* [Day 208](https://github.com/vaskoz/dailycodingproblem-go/issues/427)
diff --git a/day208/problem.go b/day208/problem.go
new file mode 100644
index 0000000..c8db110
--- /dev/null
+++ b/day208/problem.go
@@ -0,0 +1,55 @@
+package day208
+
+// SinglyLL is a singly linked list of integers.
+type SinglyLL struct {
+	Value int
+	Next  *SinglyLL
+}
+
+// PartitionSinglyLL partitions the singly linked list of
+// integers around the pivot point 'k'.
+// Runs in O(N) time and O(N) space due to new list.
+func PartitionSinglyLL(head *SinglyLL, k int) *SinglyLL {
+	leftHead := &SinglyLL{}
+	rightHead := &SinglyLL{}
+	left := leftHead
+	right := rightHead
+	for head != nil {
+		if head.Value < k {
+			left.Next = &SinglyLL{Value: head.Value}
+			left = left.Next
+		} else {
+			right.Next = &SinglyLL{Value: head.Value}
+			right = right.Next
+		}
+		head = head.Next
+	}
+	left.Next = rightHead.Next
+	return leftHead.Next
+}
+
+// PartitionSinglyLLInPlace partitions the singly linked list of
+// integers around the pivot point 'k'.
+// Runs in O(N) time and O(1) space.
+// Mutates the given list.
+func PartitionSinglyLLInPlace(head *SinglyLL, k int) *SinglyLL {
+	leftHead := &SinglyLL{}
+	rightHead := &SinglyLL{}
+	left := leftHead
+	right := rightHead
+	for head != nil {
+		nextHead := head.Next
+		if head.Value < k {
+			left.Next = head
+			left = left.Next
+			left.Next = nil
+		} else {
+			right.Next = head
+			right = right.Next
+			right.Next = nil
+		}
+		head = nextHead
+	}
+	left.Next = rightHead.Next
+	return leftHead.Next
+}


Test patch:
diff --git a/day208/problem_test.go b/day208/problem_test.go
new file mode 100644
index 0000000..5beecd8
--- /dev/null
+++ b/day208/problem_test.go
@@ -0,0 +1,91 @@
+package day208
+
+import (
+	"log"
+	"testing"
+)
+
+var testcases = []struct {
+	head     *SinglyLL
+	k        int
+	expected *SinglyLL
+}{
+	{
+		&SinglyLL{5, &SinglyLL{1, &SinglyLL{8, &SinglyLL{0, &SinglyLL{3, nil}}}}},
+		3,
+		&SinglyLL{1, &SinglyLL{0, &SinglyLL{5, &SinglyLL{8, &SinglyLL{3, nil}}}}},
+	},
+}
+
+func TestPartitionSinglyLL(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := PartitionSinglyLL(tc.head, tc.k); !equal(result, tc.expected) {
+			log.Println("Expected")
+			printLL(tc.expected)
+			log.Println("Received")
+			printLL(result)
+			t.Errorf("linked list isn't partitioned as expected for tcid%d", tcid)
+		}
+	}
+}
+
+func BenchmarkPartitionSinglyLL(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PartitionSinglyLL(tc.head, tc.k)
+		}
+	}
+}
+
+func TestPartitionSinglyLLInPlace(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		input := copied(tc.head)
+		if result := PartitionSinglyLLInPlace(input, tc.k); !equal(result, tc.expected) {
+			log.Println("Expected")
+			printLL(tc.expected)
+			log.Println("Received")
+			printLL(result)
+			t.Errorf("linked list isn't partitioned as expected for tcid%d", tcid)
+		}
+	}
+}
+
+func BenchmarkPartitionSinglyLLInPlace(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			input := copied(tc.head)
+			PartitionSinglyLLInPlace(input, tc.k)
+		}
+	}
+}
+
+func copied(a *SinglyLL) *SinglyLL {
+	head := &SinglyLL{}
+	current := head
+	for a != nil {
+		current.Next = &SinglyLL{Value: a.Value}
+		current = current.Next
+		a = a.Next
+	}
+	return head.Next
+}
+
+func printLL(a *SinglyLL) {
+	for a != nil {
+		log.Println(a)
+		a = a.Next
+	}
+}
+
+func equal(a, b *SinglyLL) bool {
+	for a != nil && b != nil {
+		if a.Value != b.Value {
+			return false
+		}
+		a = a.Next
+		b = b.Next
+	}
+	return a == nil && b == nil
+}