Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 256
Good morning! Here's your coding interview problem for today.

This problem was asked by Fitbit.

Given a linked list, rearrange the node values such that they appear in alternating `low -> high -> low -> high` ... form. For example, given `1 -> 2 -> 3 -> 4 -> 5`, you should return `1 -> 3 -> 2 -> 5 -> 4`.

Pull request:
Day256
Resolves #528.

Patch:
diff --git a/README.md b/README.md
index 7c52ce5..57a0148 100644
--- a/README.md
+++ b/README.md
@@ -267,4 +267,5 @@ problems from
 * [Day 253](https://github.com/vaskoz/dailycodingproblem-go/issues/521)
 * [Day 254](https://github.com/vaskoz/dailycodingproblem-go/issues/523)
 * [Day 255](https://github.com/vaskoz/dailycodingproblem-go/issues/525)
+* [Day 256](https://github.com/vaskoz/dailycodingproblem-go/issues/528)
 * [Day 258](https://github.com/vaskoz/dailycodingproblem-go/issues/530)
diff --git a/day256/problem.go b/day256/problem.go
new file mode 100644
index 0000000..6859fb0
--- /dev/null
+++ b/day256/problem.go
@@ -0,0 +1,30 @@
+package day256
+
+// SinglyLL is a singly linked list of integers.
+type SinglyLL struct {
+	Value int
+	Next  *SinglyLL
+}
+
+// RearrangeAlternating alternates from low->high->low.
+func RearrangeAlternating(head *SinglyLL) *SinglyLL {
+	if head == nil {
+		return nil
+	}
+	prev := head
+	curr := head.Next
+	for curr != nil {
+		if prev.Value > curr.Value {
+			prev.Value, curr.Value = curr.Value, prev.Value
+		}
+		if curr.Next != nil && curr.Next.Value > curr.Value {
+			curr.Value, curr.Next.Value = curr.Next.Value, curr.Value
+		}
+		prev = curr.Next
+		if curr.Next == nil {
+			break
+		}
+		curr = curr.Next.Next
+	}
+	return head
+}


Test patch:
diff --git a/day256/problem_test.go b/day256/problem_test.go
new file mode 100644
index 0000000..aca9dde
--- /dev/null
+++ b/day256/problem_test.go
@@ -0,0 +1,63 @@
+package day256
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	input, expected *SinglyLL
+}{
+	{nil, nil},
+	{
+		&SinglyLL{1, &SinglyLL{2, &SinglyLL{3, &SinglyLL{4, &SinglyLL{5, nil}}}}},
+		&SinglyLL{1, &SinglyLL{3, &SinglyLL{2, &SinglyLL{5, &SinglyLL{4, nil}}}}},
+	},
+	{
+		&SinglyLL{9, &SinglyLL{6, &SinglyLL{8, &SinglyLL{3, &SinglyLL{7, nil}}}}},
+		&SinglyLL{6, &SinglyLL{9, &SinglyLL{3, &SinglyLL{8, &SinglyLL{7, nil}}}}},
+	},
+	{
+		&SinglyLL{6, &SinglyLL{9, &SinglyLL{2, &SinglyLL{5, &SinglyLL{1, &SinglyLL{4, nil}}}}}},
+		&SinglyLL{6, &SinglyLL{9, &SinglyLL{2, &SinglyLL{5, &SinglyLL{1, &SinglyLL{4, nil}}}}}},
+	},
+}
+
+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 == b
+}
+
+func copyLL(a *SinglyLL) *SinglyLL {
+	newhead := &SinglyLL{}
+	curr := newhead
+	for a != nil {
+		curr.Next = &SinglyLL{a.Value, nil}
+		a = a.Next
+		curr = curr.Next
+	}
+	return newhead.Next
+}
+
+func TestRearrangeAlternating(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		input := copyLL(tc.input)
+		if result := RearrangeAlternating(input); !equal(result, tc.expected) {
+			t.Errorf("testcase #%d does not match", tcid)
+		}
+	}
+}
+
+func BenchmarkRearrangeAlternating(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			input := copyLL(tc.input)
+			RearrangeAlternating(input)
+		}
+	}
+}