Repository: keon/algorithms (python)

Issue:
separate test module
Since we now have tests in most of the algorithms, I think it is a good idea to have a separate `test_module.py` file in each module. We can move all the tests from one module to it, and any further algorithms must have their tests in this file. It will make the repo easy to manage.
@keon what do you think? I can start working on this.

Pull request description:
Separate test for linkedlist, enhance and add some problem
PR for separating test for linkedlist.
Fix #162 
I write a function convert from `Node` to `list` for testing. Now, we can use `assertEqual` in unittest. There are still some test case that need to be added. 
I am going to add some problem relating to them too. It is first draft, please review them.
@keon , @goswami-rahul 

Patch:
diff --git a/linkedlist/is_cyclic.py b/linkedlist/is_cyclic.py
index 7b9bb94..70d2c66 100644
--- a/linkedlist/is_cyclic.py
+++ b/linkedlist/is_cyclic.py
@@ -4,16 +4,12 @@ Given a linked list, determine if it has a cycle in it.
 Follow up:
 Can you solve it without using extra space?
 """
-import unittest
-
-
 class Node:
 
     def __init__(self, x):
         self.val = x
         self.next = None
 
-
 def is_cyclic(head):
     """
     :type head: Node
@@ -29,39 +25,3 @@ def is_cyclic(head):
         if runner == walker:
             return True
     return False
-
-
-class TestSuite(unittest.TestCase):
-
-    def test_is_cyclic(self):
-
-        # create linked list => A -> B -> C -> D -> E -> C
-        head = Node('A')
-        head.next = Node('B')
-        curr = head.next
-
-        cyclic_node = Node('C')
-        curr.next = cyclic_node
-
-        curr = curr.next
-        curr.next = Node('D')
-        curr = curr.next
-        curr.next = Node('E')
-        curr = curr.next
-        curr.next = cyclic_node
-
-        self.assertTrue(is_cyclic(head))
-
-        # create linked list 1 -> 2 -> 3 -> 4
-        head = Node(1)
-        curr = head
-        for i in range(2, 6):
-            curr.next = Node(i)
-            curr = curr.next
-
-        self.assertFalse(is_cyclic(head))
-
-
-if __name__ == '__main__':
-
-    unittest.main()
diff --git a/linkedlist/is_sorted.py b/linkedlist/is_sorted.py
index 5018739..978c5a6 100644
--- a/linkedlist/is_sorted.py
+++ b/linkedlist/is_sorted.py
@@ -8,15 +8,6 @@ Null :List is sorted
 1 2 3 4 :List is sorted
 1 2 -1 3 :List is not sorted
 """
-import unittest
-
-
-class Node:
-    def __init__(self, x):
-        self.val = x
-        self.next = None
-
-
 def is_sorted(head):
     if not head:
         return True
@@ -26,31 +17,3 @@ def is_sorted(head):
             return False
         current = current.next
     return True
-
-
-class TestSuite(unittest.TestCase):
-
-    def test_is_sorted(self):
-
-        head = Node(-2)
-        head.next = Node(2)
-        head.next.next = Node(2)
-        head.next.next.next = Node(4)
-        head.next.next.next.next = Node(9)
-
-        # head -> -2 -> 2 -> 2 -> 4 -> 9
-        self.assertTrue(is_sorted(head))
-
-        head = Node(1)
-        head.next = Node(2)
-        head.next.next = Node(8)
-        head.next.next.next = Node(4)
-        head.next.next.next.next = Node(6)
-
-        # head -> 1 -> 2 -> 8 -> 4 -> 6
-        self.assertFalse(is_sorted(head))
-
-
-if __name__ == "__main__":
-
-    unittest.main()
diff --git a/linkedlist/merge_two_list.py b/linkedlist/merge_two_list.py
new file mode 100644
index 0000000..6be44f3
--- /dev/null
+++ b/linkedlist/merge_two_list.py
@@ -0,0 +1,37 @@
+"""
+Merge two sorted linked lists and return it as a new list. The new list should
+be made by splicing together the nodes of the first two lists.
+
+For example:
+Input: 1->2->4, 1->3->4
+Output: 1->1->2->3->4->4
+"""
+class Node:
+
+    def __init__(self, x):
+        self.val = x
+        self.next = None
+
+def merge_two_list(l1, l2):
+    ret = cur = Node(0)
+    while l1 and l2:
+        if l1.val < l2.val:
+            cur.next = l1
+            l1 = l1.next
+        else:
+            cur.next = l2
+            l2 = l2.next
+        cur = cur.next
+    cur.next = l1 or l2
+    return ret.next
+
+# recursively
+def merge_two_list_recur(l1, l2):
+    if not l1 or not l2:
+        return l1 or l2
+    if l1.val < l2.val:
+        l1.next = merge_two_list_recur(l1.next, l2)
+        return l1
+    else:
+        l2.next = merge_two_list_recur(l1, l2.next)
+        return l2
diff --git a/linkedlist/remove_range.py b/linkedlist/remove_range.py
index b1a0e7f..ba7c144 100644
--- a/linkedlist/remove_range.py
+++ b/linkedlist/remove_range.py
@@ -9,12 +9,6 @@ List becomes: [8, 13, 17, 23, 0, 92]
 
 legal range of the list (0 < start index < end index < size of list).
 """
-
-class Node:
-    def __init__(self,x):
-        self.val = x
-        self.next = None
-
 def remove_range(head, start, end):
     assert(start <= end)
     # Case: remove node at head
@@ -32,29 +26,3 @@ def remove_range(head, start, end):
             if current != None and current.next != None:
                 current.next = current.next.next
     return head
-
-if __name__ == "__main__":
-    # Test case: middle case.
-    head = Node(None)
-    head = Node(0)
-    head.next = Node(1)
-    head.next.next = Node(2)
-    head.next.next.next = Node(3)
-    head.next.next.next.next = Node(4)
-    result = remove_range(head,1,3)  # Expect output: 0 4
-    # Test case: taking out the front node
-    head = Node(None)
-    head = Node(0)
-    head.next = Node(1)
-    head.next.next = Node(2)
-    head.next.next.next = Node(3)
-    head.next.next.next.next = Node(4)
-    result = remove_range(head,0,1)  # Expect output: 2 3 4
-    # Test case: removing all the nodes
-    head = Node(None)
-    head = Node(0)
-    head.next = Node(1)
-    head.next.next = Node(2)
-    head.next.next.next = Node(3)
-    head.next.next.next.next = Node(4)
-    result = remove_range(head,0,7)  # Expect output: Null
diff --git a/linkedlist/reverse.py b/linkedlist/reverse.py
index 93b40f4..c41b81a 100644
--- a/linkedlist/reverse.py
+++ b/linkedlist/reverse.py
@@ -1,8 +1,10 @@
 """
-Reverse a singly linked list.
-"""
-
+Reverse a singly linked list. For example:
 
+1 --> 2 --> 3 --> 4
+After reverse:
+4 --> 3 --> 2 --> 1
+"""
 #
 # Iterative solution
 # T(n)- O(n)
diff --git a/linkedlist/swap_in_pairs.py b/linkedlist/swap_in_pairs.py
index ef0ed2e..7f82f5b 100644
--- a/linkedlist/swap_in_pairs.py
+++ b/linkedlist/swap_in_pairs.py
@@ -9,37 +9,22 @@ Your algorithm should use only constant space.
 You may not modify the values in the list,
 only nodes itself can be changed.
 """
-
-
-class Node:
-    def __init__(self, x=0):
+class Node(object):
+    def __init__(self, x):
         self.val = x
         self.next = None
 
-
-def swap_pairs(head:"Node")->"Node":
+def swap_pairs(head):
     if not head:
         return head
-    start = Node()
-    pre = start
-    pre.next = head
-    while pre.next and pre.next.next:
-        a = pre.next
-        b = pre.next.next
-        pre.next, a.next, b.next = b, b.next, a
-        pre = a
+    start = Node(0)
+    start.next = head
+    current = start
+    while current.next and current.next.next:
+        first = current.next
+        second = current.next.next
+        first.next = second.next
+        current.next = second
+        current.next.next = first
+        current = current.next.next
     return start.next
-
-
-if __name__ == "__main__":
-    n = Node(1)
-    n.next = Node(2)
-    n.next.next = Node(3)
-    n.next.next.next = Node(4)
-    res = swap_pairs(n)
-
-    while res:
-        print(res.val, end=" ")
-        res = res.next
-    print("should be 2 1 4 3 ")
-


Test patch:
diff --git a/linkedlist/test_linkedlist.py b/linkedlist/test_linkedlist.py
new file mode 100644
index 0000000..dcfad55
--- /dev/null
+++ b/linkedlist/test_linkedlist.py
@@ -0,0 +1,172 @@
+from reverse import reverse_list, reverse_list_recursive
+from is_sorted import is_sorted
+from remove_range import remove_range
+from swap_in_pairs import swap_pairs
+from rotate_list import rotate_right
+from is_cyclic import is_cyclic
+from merge_two_list import merge_two_list, merge_two_list_recur
+from is_palindrome import is_palindrome, is_palindrome_stack, is_palindrome_dict
+
+import unittest
+
+class Node(object):
+    def __init__(self, x):
+        self.val = x
+        self.next = None
+
+# Convert from linked list Node to list for testing
+def convert(head):
+    ret = []
+    if head:
+        current = head
+        while current:
+            ret.append(current.val)
+            current = current.next
+    return ret
+
+class TestSuite(unittest.TestCase):
+    def setUp(self):
+        # list test for palindrome
+        self.l = Node('A')
+        self.l.next = Node('B')
+        self.l.next.next = Node('C')
+        self.l.next.next.next = Node('B')
+        self.l.next.next.next.next = Node('A')
+
+        self.l1 = Node('A')
+        self.l1.next = Node('B')
+        self.l1.next.next = Node('C')
+        self.l1.next.next.next = Node('B')
+
+    def test_reverse_list(self):
+        head = Node(1)
+        head.next = Node(2)
+        head.next.next = Node(3)
+        head.next.next.next = Node(4)
+        self.assertEqual([4, 3, 2, 1], convert(reverse_list(head)))
+        head = Node(1)
+        head.next = Node(2)
+        head.next.next = Node(3)
+        head.next.next.next = Node(4)
+        self.assertEqual([4, 3, 2, 1], convert(reverse_list_recursive(head)))
+
+    def test_is_sorted(self):
+        head = Node(-2)
+        head.next = Node(2)
+        head.next.next = Node(2)
+        head.next.next.next = Node(4)
+        head.next.next.next.next = Node(9)
+        # head -> -2 -> 2 -> 2 -> 4 -> 9
+        self.assertTrue(is_sorted(head))
+        head = Node(1)
+        head.next = Node(2)
+        head.next.next = Node(8)
+        head.next.next.next = Node(4)
+        head.next.next.next.next = Node(6)
+        # head -> 1 -> 2 -> 8 -> 4 -> 6
+        self.assertFalse(is_sorted(head))
+
+    def test_remove_range(self):
+
+        # Test case: middle case.
+        head = Node(0)
+        head.next = Node(1)
+        head.next.next = Node(2)
+        head.next.next.next = Node(3)
+        head.next.next.next.next = Node(4)
+        # Expect output: 0 4
+        self.assertEqual([0, 4], convert(remove_range(head, 1, 3)))
+
+        # Test case: taking out the front node
+        head = Node(0)
+        head.next = Node(1)
+        head.next.next = Node(2)
+        head.next.next.next = Node(3)
+        head.next.next.next.next = Node(4)
+        # Expect output: 2 3 4
+        self.assertEqual([2, 3, 4], convert(remove_range(head, 0, 1)))
+
+        # Test case: removing all the nodes
+        head = Node(0)
+        head.next = Node(1)
+        head.next.next = Node(2)
+        head.next.next.next = Node(3)
+        head.next.next.next.next = Node(4)
+        self.assertEqual([], convert(remove_range(head, 0, 7)))
+
+    def test_swap_in_pairs(self):
+        head = Node(1)
+        head.next = Node(2)
+        head.next.next = Node(3)
+        head.next.next.next = Node(4)
+        # Expect output : 2 --> 1 --> 4 --> 3
+        self.assertEqual([2, 1, 4, 3], convert(swap_pairs(head)))
+
+    def test_rotate_right(self):
+        # Given 1->2->3->4->5->NULL
+        head = Node(1)
+        head.next = Node(2)
+        head.next.next = Node(3)
+        head.next.next.next = Node(4)
+        head.next.next.next.next = Node(5)
+        # K = 2. Expect output: 4->5->1->2->3->NULL.
+        self.assertEqual([4, 5, 1, 2, 3], convert(rotate_right(head, 2)))
+
+    def test_is_cyclic(self):
+        # create linked list => A -> B -> C -> D -> E -> C
+        head = Node('A')
+        head.next = Node('B')
+        curr = head.next
+        cyclic_node = Node('C')
+        curr.next = cyclic_node
+        curr = curr.next
+        curr.next = Node('D')
+        curr = curr.next
+        curr.next = Node('E')
+        curr = curr.next
+        curr.next = cyclic_node
+        self.assertTrue(is_cyclic(head))
+
+        # create linked list 1 -> 2 -> 3 -> 4
+        head = Node(1)
+        curr = head
+        for i in range(2, 6):
+            curr.next = Node(i)
+            curr = curr.next
+        self.assertFalse(is_cyclic(head))
+
+    def test_merge_two_list(self):
+        """
+        Input: head1:1->2->4, head2: 1->3->4
+        Output: 1->1->2->3->4->4
+        """
+        head1 = Node(1)
+        head1.next = Node(2)
+        head1.next.next = Node(4)
+        head2 = Node(1)
+        head2.next = Node(3)
+        head2.next.next = Node(4)
+        self.assertEqual([1, 1, 2, 3, 4, 4],
+                         convert(merge_two_list(head1, head2)))
+        # Test recursive
+        head1 = Node(1)
+        head1.next = Node(2)
+        head1.next.next = Node(4)
+        head2 = Node(1)
+        head2.next = Node(3)
+        head2.next.next = Node(4)
+        self.assertEqual([1, 1, 2, 3, 4, 4],
+                         convert(merge_two_list_recur(head1, head2)))
+
+    def test_is_palindrome(self):
+        self.assertTrue(is_palindrome(self.l))
+        self.assertFalse(is_palindrome(self.l1))
+    def test_is_palindrome_stack(self):
+        self.assertTrue(is_palindrome_stack(self.l))
+        self.assertFalse(is_palindrome_stack(self.l1))
+    def test_is_palindrome_dict(self):
+        self.assertTrue(is_palindrome_dict(self.l))
+        self.assertFalse(is_palindrome_dict(self.l1))
+
+if __name__ == "__main__":
+    unittest.main()