aboutsummaryrefslogtreecommitdiff
path: root/remove_nodes_linked_list.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /remove_nodes_linked_list.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'remove_nodes_linked_list.c')
-rw-r--r--remove_nodes_linked_list.c59
1 files changed, 59 insertions, 0 deletions
diff --git a/remove_nodes_linked_list.c b/remove_nodes_linked_list.c
new file mode 100644
index 0000000..0bcae4f
--- /dev/null
+++ b/remove_nodes_linked_list.c
@@ -0,0 +1,59 @@
+// 2487. Remove Nodes From Linked List
+#include "leetcode.h"
+
+/*
+ * given the 'head' of a linked list, remove evey node which has a node with a
+ * greater value anywhere to the right side of it. return the 'head' of the
+ * modified linked list.
+ */
+
+struct ListNode {
+ int val;
+ struct ListNode *next;
+};
+
+int depth(struct ListNode *head) {
+ int n = 0;
+ struct ListNode *tmp = head;
+ while (tmp) {
+ n++;
+ tmp = tmp->next;
+ }
+ return n;
+}
+
+struct ListNode *removeNodes(struct ListNode *head) {
+ int n = depth(head), i = 0;
+ struct ListNode **arr =
+ (struct ListNode **)malloc(n * sizeof(struct ListNode *));
+ struct ListNode *tmp = head;
+ while (tmp) {
+ arr[i] = tmp;
+ i++;
+ tmp = tmp->next;
+ }
+ bool *remove = (bool *)calloc(n, sizeof(bool));
+ int max = arr[n - 1]->val;
+ for (int i = n - 2; i >= 0; i--) {
+ if (arr[i]->val < max)
+ remove[i] = true;
+ else if (arr[i]->val > max)
+ max = arr[i]->val;
+ }
+ struct ListNode *ans;
+ for (int i = 0; i < n; i++) {
+ if (!remove[i]) {
+ ans = arr[i];
+ tmp = ans;
+ for (int j = i + 1; j < n; j++)
+ if (!remove[j]) {
+ tmp->next = arr[j];
+ tmp = tmp->next;
+ }
+ tmp->next = NULL;
+ break;
+ }
+ }
+ free(arr), free(remove);
+ return ans;
+}