Initial commit.HEADmain

7 files changed, 272 insertions, 0 deletions

diff --git a/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc b/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc
new file mode 100644
index 0000000..47f9559
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc
@@ -0,0 +1,22 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    void deleteNode(ListNode* node) {
+        while (node) {
+            if (node->next) {
+                node->val = node->next->val;
+                if (!node->next->next) {
+                    node->next = NULL;
+                }
+            }
+            node = node->next;
+        }
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc b/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc
new file mode 100644
index 0000000..6773f04
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc
@@ -0,0 +1,32 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Return the number of elements in the list.
+    int removeNth(ListNode* node, int n) {
+        if (!node) {
+            return 0;
+        }
+        const int tailLength = removeNth(node->next, n);
+        if (tailLength == n) {
+            node->next = node->next->next;
+        }
+        return tailLength + 1;
+    }
+
+    ListNode* removeNthFromEnd(ListNode* head, int n) {
+        const int listLength = removeNth(head, n);
+        if (listLength == n) {
+            head = head->next;
+        }
+        return head;
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc b/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc
new file mode 100644
index 0000000..d97bd33
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc
@@ -0,0 +1,26 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Reverse the list and return the head of the new list.
+    ListNode* reverse(ListNode* node) {
+        if (!node)       { return nullptr; }
+        if (!node->next) { return node; }
+        ListNode* head = reverse(node->next);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    ListNode* reverseList(ListNode* head) {
+        return reverse(head);
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc b/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc
new file mode 100644
index 0000000..9724ef0
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc
@@ -0,0 +1,52 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
+        ListNode* mergedHead = nullptr;
+        ListNode* merged     = nullptr;
+        while (list1 && list2) {
+            if (list1->val <= list2->val) {
+                if (merged) {
+                    merged->next = list1;
+                    merged = merged->next;
+                } else {
+                    merged = list1;
+                    mergedHead = merged;
+                }
+                list1 = list1->next;
+            } else {
+                if (merged) {
+                    merged->next = list2;
+                    merged = merged->next;
+                } else {
+                    merged = list2;
+                    mergedHead = merged;
+                }
+                list2 = list2->next;
+            }
+        }
+        if (list1) {
+            if (merged) {
+                merged->next = list1;
+            } else {
+                mergedHead = list1;
+            }
+        } else if (list2) {
+            if (merged) {
+                merged->next = list2;
+            } else {
+                mergedHead = list2;
+            }
+        }
+        return mergedHead;
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc b/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc
new file mode 100644
index 0000000..3f42e4a
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc
@@ -0,0 +1,48 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Copy the list.
+    ListNode* clone(const ListNode* node) {
+        if (!node) return nullptr;
+        ListNode* copy = new ListNode();
+        copy->val = node->val;
+        if (node->next) {
+            copy->next = clone(node->next);
+        } else {
+            copy->next = nullptr;
+        }
+        return copy;
+    }
+
+    // Reverse a list and return the new of the reversed list.
+    ListNode* reverse(ListNode* node) {
+        if (!node)       return nullptr;
+        if (!node->next) return node;
+        ListNode* head = reverse(node->next);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    // Compare two lists for equality.
+    bool eq(const ListNode* a, const LideNode* b) {
+        if (!a && !b)         return true;
+        if (!a)               return false;
+        if (!b)               return false;
+        if (a->val != b->val) return false;
+        return eq(a->next, b->next);
+    }
+
+    bool isPalindrome(ListNode* head) {
+        return eq(head, reverse(clone(head)));
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc b/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc
new file mode 100644
index 0000000..590c485
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc
@@ -0,0 +1,63 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Return the length of the list.
+    size_t length(const ListNode* node) {
+        if (!node) return 0;
+        return 1 + length(node->next);
+    }
+
+    // Return the nth element of the list.
+    const ListNode* nth(const ListNode* node, size_t n) {
+        if (!node)  return nullptr;
+        if (n == 0) return node;
+        return nth(node->next, n-1);
+    }
+
+    // Reverse the list up to, and not including, the nth element.
+    // Return the head of the reversed list (nth-1 node).
+    ListNode* reverse(ListNode* node, size_t n) {
+        if (!node)       return nullptr;
+        if (!node->next) return node;
+        if (n == 1) {
+            node->next = nullptr;
+            return node;
+        }
+
+        ListNode* head = reverse(node->next, n-1);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    // Compare two lists for equality.
+    bool eq(const ListNode* a, const ListNode* b) {
+        if (!a && !b)         return true;
+        if (!a)               return false;
+        if (!b)               return false;
+        if (a->val != b->val) return false;
+        return eq(a->next, b->next);
+    }
+
+    bool isPalindrome(ListNode* head) {
+        if (!head)       return true;
+        if (!head->next) return true;
+
+        // If odd,  get the middle element.
+        // If even, get the first element of the second half.
+        const size_t len      = length(head);
+        const size_t middle   = len/2;
+        const ListNode* head1 = nth(head, middle + (len & 1));
+        const ListNode* head2 = reverse(head, middle);
+        return eq(head1, head2);
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc b/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc
new file mode 100644
index 0000000..e8b4d1d
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc
@@ -0,0 +1,29 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    bool hasCycle(ListNode *head) {
+        if (!head)       return false;
+        if (!head->next) return false;
+
+        const ListNode* next1 = head;
+        const ListNode* next2 = head;
+
+        do {
+            next1 = next1->next;
+            next2 = next2->next;
+            if (next2) {
+                next2 = next2->next;
+            }
+        }
+        while ((next1 != head) && next1 && next2 && (next1 != next2));
+
+        return next1 && next2 && (next1 == next2);
+    }
+};