Updated 8 solutions.

oscarjz · Mar 22, 2019 · f0deb45 · f0deb45
1 parent 60d84d6
commit f0deb45
Show file tree

Hide file tree

Showing 8 changed files with 25 additions and 21 deletions.
diff --git a/Algorithms/Bit Manipulation/Sansa and XOR/Solution.java b/Algorithms/Bit Manipulation/Sansa and XOR/Solution.java
@@ -27,6 +27,7 @@
 // in the original array to get our final answer.
 
 //  Time Complexity: O(n)
+// Space Complexity: O(1)
 
 static int sansaXor(int[] array) {
     if (array.length % 2 == 0) { // Case 1

diff --git a/Cracking the Coding Interview/Data Structures/Linked Lists - Detect a Cycle/Solution.java b/Cracking the Coding Interview/Data Structures/Linked Lists - Detect a Cycle/Solution.java
@@ -2,8 +2,13 @@
 //     Github: github.com/RodneyShag
 // HackerRank: hackerrank.com/RodneyShag
 
+// Algorithm
+//
+// 1. Create a pointer that moves 1 step  at a time: 'slow'
+// 2. Create a pointer that moves 2 steps at a time: 'fast'
+// 3. If the Linked List has a cycle, 'slow' and 'fast' will collide.
+
 /*
-Detect a cycle in a linked list. Note that the head pointer may be 'null' if the list is empty.
 
 A Node is defined as: 
     class Node {
@@ -30,3 +35,6 @@ boolean hasCycle(Node head) {
     }
     return false;
 }
+
+//  Time Complexity: O(n)
+// Space Complexity: O(1)
diff --git a/Cracking the Coding Interview/Data Structures/Stacks - Balanced Brackets/Solution.java b/Cracking the Coding Interview/Data Structures/Stacks - Balanced Brackets/Solution.java
@@ -4,6 +4,9 @@
 
 // ArrayDeque is "likely to be faster than Stack when used as a stack" - Java documentation
 
+//  Time Complexity: O(n)
+// Space Complexity: O(n)
+
 /* Create HashMap to match opening brackets with closing brackets */
 static String isBalanced(String expression) {
     HashMap<Character, Character> map = new HashMap<>();

diff --git a/...g the Coding Interview/Data Structures/Trees - Is This a Binary Search Tree/Solution.java b/...g the Coding Interview/Data Structures/Trees - Is This a Binary Search Tree/Solution.java
@@ -2,7 +2,7 @@
 //     Github: github.com/RodneyShag
 // HackerRank: hackerrank.com/RodneyShag
 
-/* Hidden stub code will pass a root argument to the function below. 
+/* 
 
 The Node class is defined as follows:
     class Node {

diff --git a/Data Structures/Linked Lists/Merge two sorted linked lists/Solution.java b/Data Structures/Linked Lists/Merge two sorted linked lists/Solution.java
@@ -3,35 +3,24 @@
 // HackerRank: hackerrank.com/RodneyShag
 
 /*
-  Node is defined as 
-  class Node {
+  class SinglyLinkedListNode {
      int data;
-     Node next;
+     SinglyLinkedListNode next;
   }
 */
 
 //  Time Complexity: O(n + m)
 // Space Complexity: O(1)
 
-Node MergeLists(Node currA, Node currB) {
+static SinglyLinkedListNode mergeLists(SinglyLinkedListNode currA, SinglyLinkedListNode currB) {
     if (currA == null) {
         return currB;
     } else if (currB == null) {
         return currA;
     }
 
-    /* Find new head pointer */
-    Node head = null;
-    if (currA.data < currB.data) {
-        head = currA;
-        currA = currA.next;
-    } else {
-        head = currB;
-        currB = currB.next;
-    }
-
-    /* Build rest of list */
-    Node n = head;
+    SinglyLinkedListNode result = new SinglyLinkedListNode(0); // dummy/placeholder ListNode
+    SinglyLinkedListNode n = result;
     while (currA != null && currB != null) {
         if (currA.data < currB.data) {
             n.next = currA;
@@ -50,5 +39,5 @@ Node MergeLists(Node currA, Node currB) {
         n.next = currA;
     }
 
-    return head;
+    return result.next;
 }
diff --git a/Data Structures/Linked Lists/Reverse a doubly linked list/Solution.java b/Data Structures/Linked Lists/Reverse a doubly linked list/Solution.java
@@ -16,7 +16,7 @@
 //  Time Complexity: O(n)
 // Space Complexity: O(1)
 DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
-    if (head == null && head.next == null) {
+    if (head == null || head.next == null) {
         return head;
     }
     DoublyLinkedListNode prev = null;

diff --git a/Data Structures/Linked Lists/Reverse a linked list/Solution.java b/Data Structures/Linked Lists/Reverse a linked list/Solution.java
@@ -17,7 +17,7 @@
  */
 
 static SinglyLinkedListNode reverse(SinglyLinkedListNode head) {
-    if (head == null && head.next == null) {
+    if (head == null || head.next == null) {
         return head;
     }
     SinglyLinkedListNode prev = null;

diff --git a/Data Structures/Stacks/Balanced Brackets/Solution.java b/Data Structures/Stacks/Balanced Brackets/Solution.java
@@ -8,6 +8,9 @@
 
 // ArrayDeque is "likely to be faster than Stack when used as a stack" - Java documentation
 
+//  Time Complexity: O(n)
+// Space Complexity: O(n)
+
 public class Solution {
     public static void main(String[] args) {
         /* Create HashMap to match opening brackets with closing brackets */