about summary refs log tree commit diff
path: root/deepmind/reverse-linked-list.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-01-22T11·05+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-01-22T11·05+0000
commit4f6191b34cb0f29ece4930ee7279048cba7e33f2 (patch)
tree8553bd5c031a2491a83eb1c04e024cbf9b35e66e /deepmind/reverse-linked-list.py
parent2a0540d76da26497d4600e9666bb6f36355357c1 (diff)
Complete reverse-linked-list problem
Completing the deceptively tricky reverse-linked-list problem from
InterviewCake.com.
Diffstat (limited to 'deepmind/reverse-linked-list.py')
-rw-r--r--deepmind/reverse-linked-list.py74
1 files changed, 74 insertions, 0 deletions
diff --git a/deepmind/reverse-linked-list.py b/deepmind/reverse-linked-list.py
new file mode 100644
index 000000000000..82fac171d5d1
--- /dev/null
+++ b/deepmind/reverse-linked-list.py
@@ -0,0 +1,74 @@
+import unittest
+
+
+def reverse(node):
+    prev = None
+    next = None
+    curr = node
+
+    while curr:
+        next = curr.next
+        curr.next = prev
+        prev = curr
+        curr = next
+
+    return prev
+
+
+# Tests
+class Test(unittest.TestCase):
+    class LinkedListNode(object):
+        def __init__(self, value, next=None):
+            self.value = value
+            self.next = next
+
+        def get_values(self):
+            node = self
+            values = []
+            while node is not None:
+                values.append(node.value)
+                node = node.next
+            return values
+
+    def test_short_linked_list(self):
+        second = Test.LinkedListNode(2)
+        first = Test.LinkedListNode(1, second)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [2, 1]
+        self.assertEqual(actual, expected)
+
+    def test_long_linked_list(self):
+        sixth = Test.LinkedListNode(6)
+        fifth = Test.LinkedListNode(5, sixth)
+        fourth = Test.LinkedListNode(4, fifth)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [6, 5, 4, 3, 2, 1]
+        self.assertEqual(actual, expected)
+
+    def test_one_element_linked_list(self):
+        first = Test.LinkedListNode(1)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [1]
+        self.assertEqual(actual, expected)
+
+    def test_empty_linked_list(self):
+        result = reverse(None)
+        self.assertIsNone(result)
+
+
+unittest.main(verbosity=2)