From 4689e4e80b479be25f7557d05818f5caa723aafa Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Wed, 5 Feb 2025 18:36:31 -0800 Subject: Initial commit. --- .../linked_list/01_delete_node_in_a_linked_list.cc | 22 ++++++++ .../02_remove_nth_node_from_end_of_list.cc | 32 +++++++++++ .../easy/linked_list/03_reverse_linked_list.cc | 26 +++++++++ .../easy/linked_list/04_merge_two_sorted_lists.cc | 52 ++++++++++++++++++ .../easy/linked_list/05_palindrome_linked_list.cc | 48 +++++++++++++++++ .../linked_list/05_palindrome_linked_list_2.cc | 63 ++++++++++++++++++++++ .../easy/linked_list/06_linked_list_cycle.cc | 29 ++++++++++ 7 files changed, 272 insertions(+) create mode 100644 top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc create mode 100644 top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc create mode 100644 top-interview-questions/easy/linked_list/03_reverse_linked_list.cc create mode 100644 top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc create mode 100644 top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc create mode 100644 top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc create mode 100644 top-interview-questions/easy/linked_list/06_linked_list_cycle.cc (limited to 'top-interview-questions/easy/linked_list') 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); + } +}; -- cgit v1.2.3