aboutsummaryrefslogtreecommitdiff
path: root/partition_list.c
blob: a95b1d997ed5f0ef8facfb4331e43725b60e6ec7 (plain)
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
// 86. Partition List
#include <stdlib.h>

/*
 * given the head of a linked list and a value 'x', partition it such that all
 * nodes less than 'x' come before nodes greater than or equal to 'x'. you
 * should preserve the original relative order of the nodes in each of the two
 * partitions.
 */

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *add(struct ListNode *head, int data) {
  struct ListNode *tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
  tmp->val = data;
  tmp->next = NULL;
  if (!head) {
    head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = data;
    head->next = NULL;
  } else {
    struct ListNode *traverse = head;
    while (traverse)
      traverse = traverse->next;
    traverse->next = tmp;
  }
  return head;
}

struct ListNode *partition(struct ListNode *head, int x) {
  if (!head)
    return head;
  int *arr = (int *)malloc(200 * sizeof(int));
  struct ListNode *traverse = head;
  int idx = 0, is_head = 0;
  if (traverse->val >= x) {
    arr[idx++] = traverse->val;
    is_head = 1;
  }
  while (traverse && traverse->next) {
    if (traverse->next->val >= x) {
      arr[idx++] = traverse->next->val;
      traverse->next = traverse->next->next;
    } else {
      traverse = traverse->next;
    }
  }
  struct ListNode *res = head;
  while (res && res->next)
    res = res->next;
  for (int i = 0; i < idx; i++)
    res = add(res, arr[i]);
  if (is_head == 1)
    head = head->next;
  return head;
}