Add solution and test case for 1721 (#158)

ashmichheda · web-flow · commit 59d19a27a8d7 · 2021-08-28T07:57:03.000-07:00
* added solution and test case for 1721

* merged with master

* removed comments and initialized variables on new lines

* add solution and testcase for 1721
diff --git a/src/main/java/com/fishercoder/solutions/_1721.java b/src/main/java/com/fishercoder/solutions/_1721.java
@@ -69,4 +69,39 @@ public ListNode swapNodes(ListNode head, int k) {
             return dummy.next;
         }
     }
+    public static class Solution3 {
+        public ListNode swapNodes(ListNode head, int k) {
+            // O(n) linear time
+            /*
+                1. Calculate length of linked list
+                2. Initialize 3 ptrs, temp1 and temp2 used for pointing to nodes at k, (len - k + 1)
+                and temp3 used to iterate over the linked list
+             */
+            int length = 0;
+            int secondIndex;
+
+            ListNode temp1 = null, temp2 = null;
+            ListNode temp3 = head;
+            while(temp3 != null){
+                length++;
+                temp3 = temp3.next;
+            }
+
+            secondIndex = length - k + 1;
+            temp3 = head;
+            for(int i = 1; i <= length; i++){
+                if(i == k){
+                    temp1 = temp3;
+                }
+                if(i == secondIndex){
+                    temp2 = temp3;
+                }
+                temp3 = temp3.next;
+            }
+            int value = temp1.val;
+            temp1.val = temp2.val;
+            temp2.val = value;
+            return head;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1721Test.java b/src/test/java/com/fishercoder/_1721Test.java
@@ -9,8 +9,9 @@
 import static org.junit.Assert.assertEquals;
 
 public class _1721Test {
-    private static _1721.Solution1 solution1;
     private static _1721.Solution2 solution2;
+    private static _1721.Solution3 solution3;
+    private static _1721.Solution1 solution1;
     private static ListNode expected;
     private static ListNode node;
     private static int k;
@@ -19,21 +20,38 @@ public class _1721Test {
     public static void setup() {
         solution1 = new _1721.Solution1();
         solution2 = new _1721.Solution2();
+        solution3 = new _1721.Solution3();
     }
 
     @Test
     public void test1() {
-        node = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5});
-        expected = LinkedListUtils.contructLinkedList(new int[]{1, 4, 3, 2, 5});
+        node = new ListNode(1);
+        node.next = new ListNode(2);
+        node.next.next = new ListNode(3);
+        node.next.next.next = new ListNode(4);
+        node.next.next.next.next = new ListNode(5);
+
+        expected = new ListNode(1);
+        expected.next = new ListNode(4);
+        expected.next.next = new ListNode(3);
+        expected.next.next.next = new ListNode(2);
+        expected.next.next.next.next = new ListNode(5);
+
         k = 2;
-        assertEquals(expected, solution1.swapNodes(node, k));
+        assertEquals(expected, solution2.swapNodes(node, k));
     }
-
     @Test
     public void test2() {
         node = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5});
         expected = LinkedListUtils.contructLinkedList(new int[]{1, 4, 3, 2, 5});
         k = 2;
         assertEquals(expected, solution2.swapNodes(node, k));
     }
+    @Test
+      public void test3(){
+          node = LinkedListUtils.contructLinkedList(new int[]{90, 100});
+          k = 2;
+          expected = LinkedListUtils.contructLinkedList(new int[]{100, 90});
+          assertEquals(expected, solution3.swapNodes(node, k));
+      }
 }
