Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 104
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Determine whether a doubly linked list is a palindrome. What if it’s singly linked?

For example, `1 -> 4 -> 3 -> 4 -> 1` returns `true` while `1 -> 4` returns `false`.

Pull request:
Day104
Resolves #219.

Patch:
diff --git a/README.md b/README.md
index 710675e..4c264ef 100644
--- a/README.md
+++ b/README.md
@@ -113,3 +113,4 @@ problems from
 * [Day 101](https://github.com/vaskoz/dailycodingproblem-go/issues/212)
 * [Day 102](https://github.com/vaskoz/dailycodingproblem-go/issues/214)
 * [Day 103](https://github.com/vaskoz/dailycodingproblem-go/issues/217)
+* [Day 104](https://github.com/vaskoz/dailycodingproblem-go/issues/219)
diff --git a/day104/problem.go b/day104/problem.go
new file mode 100644
index 0000000..70b27bf
--- /dev/null
+++ b/day104/problem.go
@@ -0,0 +1,97 @@
+package day104
+
+// DoublyLL is a doubly linked list.
+type DoublyLL struct {
+	Value      int
+	Prev, Next *DoublyLL
+}
+
+// SinglyLL is a singly linked list.
+type SinglyLL struct {
+	Value int
+	Next  *SinglyLL
+}
+
+// IsPalindromeDoublyLL answers the question "is this list a palindrome?".
+// Runs on a doubly linked list.
+// Runs in O(N) time and O(1) extra space.
+func IsPalindromeDoublyLL(head *DoublyLL) bool {
+	var n int
+	var tail *DoublyLL
+	for tail = head; tail.Next != nil; tail = tail.Next {
+		n++
+	}
+	n++
+	for i := 0; i < n/2; i++ {
+		if head.Value != tail.Value {
+			return false
+		}
+		head = head.Next
+		tail = tail.Prev
+	}
+	return true
+}
+
+// IsPalindromeSinglyLLStack answers the question "is this list a palindrome?".
+// Runs on a singly linked list.
+// Runs in O(N) time and O(N) space.
+func IsPalindromeSinglyLLStack(head *SinglyLL) bool {
+	var n int
+	var data []int
+	for tail := head; tail != nil; tail = tail.Next {
+		data = append(data, tail.Value)
+		n++
+	}
+	for i := range data {
+		if head == nil || head.Value != data[len(data)-1-i] {
+			return false
+		}
+		head = head.Next
+	}
+	return head == nil
+}
+
+// IsPalindromeSinglyLLReverse answers the question "is this list a palindrome?".
+// Runs on a singly linked list.
+// Runs in O(N) time and O(1) space.
+// NOTE: This modifies the linked list during execution, but restores it after completion.
+func IsPalindromeSinglyLLReverse(head *SinglyLL) bool {
+	var n int
+	for tail := head; tail != nil; tail = tail.Next {
+		n++
+	}
+	halfPoint := head
+	for i := 0; i < (n/2)-1; i++ {
+		halfPoint = halfPoint.Next
+	}
+	if n%2 == 1 {
+		halfPoint = halfPoint.Next
+	}
+	reversed := ReverseSinglyLL(halfPoint.Next)
+	halfPoint.Next = reversed
+	isPalindrome := true
+	half := halfPoint.Next
+	for i := 0; i < n/2; i++ {
+		if half.Value != head.Value {
+			isPalindrome = false
+			break
+		}
+		half = half.Next
+		head = head.Next
+	}
+	halfPoint.Next = ReverseSinglyLL(halfPoint.Next)
+	return isPalindrome
+}
+
+// ReverseSinglyLL reverses a singly linked list in O(1) space
+// and O(N) time.
+func ReverseSinglyLL(head *SinglyLL) *SinglyLL {
+	var reversed *SinglyLL
+	for head != nil {
+		next := head.Next
+		head.Next = reversed
+		reversed = head
+		head = next
+	}
+	return reversed
+}


Test patch:
diff --git a/day104/problem_test.go b/day104/problem_test.go
new file mode 100644
index 0000000..fff9b1a
--- /dev/null
+++ b/day104/problem_test.go
@@ -0,0 +1,96 @@
+package day104
+
+import "testing"
+
+var testcases = []struct {
+	data         []int
+	isPalindrome bool
+}{
+	{[]int{1, 4, 3, 4, 1}, true},
+	{[]int{1, 4}, false},
+}
+
+func TestIsPalindromeDoublyLL(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		head := createDoublyLL(tc.data)
+		if result := IsPalindromeDoublyLL(head); result != tc.isPalindrome {
+			t.Errorf("For input %v expected %v got %v", tc.data, tc.isPalindrome, result)
+		}
+	}
+}
+
+func BenchmarkIsPalindromeDoublyLL(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			head := createDoublyLL(tc.data)
+			IsPalindromeDoublyLL(head)
+		}
+	}
+}
+
+func TestIsPalindromeSinglyLLStack(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		head := createSinglyLL(tc.data)
+		if result := IsPalindromeSinglyLLStack(head); result != tc.isPalindrome {
+			t.Errorf("For input %v expected %v got %v", tc.data, tc.isPalindrome, result)
+		}
+	}
+}
+
+func BenchmarkIsPalindromeSinglyLLStack(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			head := createSinglyLL(tc.data)
+			IsPalindromeSinglyLLStack(head)
+		}
+	}
+}
+
+func TestIsPalindromeSinglyLLReverse(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		head := createSinglyLL(tc.data)
+		if result := IsPalindromeSinglyLLReverse(head); result != tc.isPalindrome {
+			t.Errorf("For input %v expected %v got %v", tc.data, tc.isPalindrome, result)
+		}
+	}
+}
+
+func BenchmarkIsPalindromeSinglyLLReverse(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			head := createSinglyLL(tc.data)
+			IsPalindromeSinglyLLReverse(head)
+		}
+	}
+}
+
+func createDoublyLL(input []int) *DoublyLL {
+	if len(input) == 0 {
+		return nil
+	}
+	head := &DoublyLL{input[0], nil, nil}
+	current := head
+	for i := 1; i < len(input); i++ {
+		next := &DoublyLL{Value: input[i], Prev: current, Next: nil}
+		current.Next = next
+		current = next
+	}
+	return head
+}
+
+func createSinglyLL(input []int) *SinglyLL {
+	if len(input) == 0 {
+		return nil
+	}
+	head := &SinglyLL{input[0], nil}
+	current := head
+	for i := 1; i < len(input); i++ {
+		next := &SinglyLL{input[i], nil}
+		current.Next = next
+		current = next
+	}
+	return head
+}