leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

remove_nodes_linked_list.c (1290B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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;
}