src/lib/ll.c

   1 #include "src/lib/ll.h"\r
   2 \r
   3 #ifdef OTHERMERGELISTSTIFF\r
   4 int listLength(node_t * item)\r
   5 {\r
   6   node_t * cur = item;\r
   7   int size = 0;\r
   8 \r
   9   while (cur->next != NULL)\r
  10   {\r
  11          ++size;\r
  12          cur = cur->next;\r
  13   }\r
  14 \r
  15   return size;\r
  16 }\r
  17 \r
  18 void print_list(node_t * head)\r
  19 {\r
  20         node_t * current = head;\r
  21 \r
  22         while (current->next != NULL)\r
  23         {\r
  24                 printf("[%u]=   %d\n", current->id, current->val);\r
  25                 current = current->next;\r
  26         }\r
  27 }\r
  28 \r
  29 void pushe(node_t * head, int val)\r
  30 {\r
  31         node_t * current = head;\r
  32         current->id = head->id;\r
  33         current->next->id = current->id+1;\r
  34 \r
  35         while (current->next != NULL)\r
  36         {\r
  37                 current->next->id = current->id;\r
  38                 current = current->next;\r
  39                 current->id++;\r
  40         }\r
  41 \r
  42         // now we can add a new variable\r
  43         current->next = malloc(sizeof(node_t));\r
  44         current->next->val = val;\r
  45         current->next->next = NULL;\r
  46         current->next->id++;\r
  47 }\r
  48 \r
  49 void pushs(node_t ** head, int val)\r
  50 {\r
  51         node_t * new_node;\r
  52         new_node = malloc(sizeof(node_t));\r
  53 \r
  54         new_node->val = val;\r
  55         new_node->next = *head;\r
  56         *head = new_node;\r
  57 }\r
  58 \r
  59 int pop(node_t ** head)\r
  60 {\r
  61         int retval = -1;\r
  62         node_t * next_node = NULL;\r
  63 \r
  64         if (*head == NULL) {\r
  65                 return -1;\r
  66         }\r
  67 \r
  68         next_node = (*head)->next;\r
  69         retval = (*head)->val;\r
  70         free(*head);\r
  71         *head = next_node;\r
  72 \r
  73         return retval;\r
  74 }\r
  75 \r
  76 int remove_last(node_t * head)\r
  77 {\r
  78         int retval = 0;\r
  79         node_t * current;\r
  80 \r
  81         /* if there is only one item in the list, remove it */\r
  82         if (head->next == NULL) {\r
  83                 retval = head->val;\r
  84                 free(head);\r
  85                 return retval;\r
  86         }\r
  87 \r
  88         /* get to the last node in the list */\r
  89         current = head;\r
  90         while (current->next->next != NULL) {\r
  91                 current = current->next;\r
  92         }\r
  93 \r
  94         /* now current points to the last item of the list, so let's remove current->next */\r
  95         retval = current->next->val;\r
  96         free(current->next);\r
  97         current->next = NULL;\r
  98         return retval;\r
  99 \r
 100 }\r
 101 \r
 102 int remove_by_index(node_t ** head, int n)\r
 103 {\r
 104         int i = 0;\r
 105         int retval = -1;\r
 106         node_t * current = *head;\r
 107         node_t * temp_node = NULL;\r
 108 \r
 109         if (n == 0) {\r
 110                 return pop(head);\r
 111         }\r
 112 \r
 113         for (i = 0; i < n-1; i++) {\r
 114                 if (current->next == NULL) {\r
 115                         return -1;\r
 116                 }\r
 117                 current = current->next;\r
 118         }\r
 119 \r
 120         temp_node = current->next;\r
 121         retval = temp_node->val;\r
 122         current->next = temp_node->next;\r
 123         free(temp_node);\r
 124 \r
 125         return retval;\r
 126 }\r
 127 #else\r
 128 /* Takes two lists sorted in increasing order, and splices\r
 129         their nodes together to make one big sorted list which\r
 130         is returned.    */\r
 131 struct node* SortedMerge(struct node* a, struct node* b)\r
 132 {\r
 133         /* a dummy first node to hang the result on */\r
 134         struct node dummy;\r
 135 \r
 136         /* tail points to the last result node  */\r
 137         struct node* tail = &dummy;\r
 138 \r
 139         /* so tail->next is the place to add new nodes\r
 140           to the result. */\r
 141         dummy.next = NULL;\r
 142         while (1)\r
 143         {\r
 144                 if (a == NULL)\r
 145                 {\r
 146                         /* if either list runs out, use the\r
 147                                 other list */\r
 148                         tail->next = b;\r
 149                         break;\r
 150                 }\r
 151                 else if (b == NULL)\r
 152                 {\r
 153                         tail->next = a;\r
 154                         break;\r
 155                 }\r
 156                 if (a->data <= b->data)\r
 157                         Movenode(&(tail->next), &a);\r
 158                 else\r
 159                         Movenode(&(tail->next), &b);\r
 160 \r
 161                 tail = tail->next;\r
 162         }\r
 163         return(dummy.next);\r
 164 }\r
 165 \r
 166 struct node* LL_merge(struct node* a, struct node* b)\r
 167 {\r
 168         /* a dummy first node to hang the result on */\r
 169         struct node dummy;\r
 170 \r
 171         /* tail points to the last result node  */\r
 172         struct node* tail = &dummy;\r
 173 \r
 174         /* so tail->next is the place to add new nodes\r
 175           to the result. */\r
 176         dummy.next = NULL;\r
 177         Movenode(&(tail->next), &a);\r
 178         a = a->next;\r
 179         tail = tail->next;\r
 180         while (1)\r
 181         {\r
 182                 if (a == NULL)\r
 183                 {\r
 184                         /* if either list runs out, use the\r
 185                                 other list */\r
 186                         tail->next = b;\r
 187                         break;\r
 188                 }\r
 189                 else if (b == NULL)\r
 190                 {\r
 191                         tail->next = a;\r
 192                         break;\r
 193                 }\r
 194                 if (a->data <= b->data)\r
 195                         Movenode(&(tail->next), &a);\r
 196                 else\r
 197                         Movenode(&(tail->next), &b);\r
 198 \r
 199                 tail = tail->next;\r
 200         }\r
 201         return(dummy.next);\r
 202 }\r
 203 \r
 204 /* The function removes duplicates from a sorted list */\r
 205 void removeDuplicates(struct node* head)\r
 206 {\r
 207         /* Pointer to traverse the linked list */\r
 208         struct node* current = head;\r
 209  \r
 210         /* Pointer to store the next pointer of a node to be deleted*/\r
 211         struct node* next_next;\r
 212 \r
 213         /* do nothing if the list is empty */\r
 214         if (current == NULL)\r
 215                 return;\r
 216  \r
 217         /* Traverse the list till last node */\r
 218         while (current->next != NULL)\r
 219         {\r
 220                 /* Compare current node with next node */\r
 221                 if (current->data == current->next->data)\r
 222                 {\r
 223                         /* The sequence of steps is important */\r
 224                         next_next = current->next->next;\r
 225                         free(current->next);\r
 226                         current->next = next_next;\r
 227                 }\r
 228                 else /* This is tricky: only advance if no deletion */\r
 229                 {\r
 230                   current = current->next;\r
 231                 }\r
 232         }\r
 233 }\r
 234 \r
 235 /* UTILITY FUNCTIONS */\r
 236 /* Movenode() function takes the node from the front of the\r
 237         source, and move it to the front of the dest.\r
 238         It is an error to call this with the source list empty.\r
 239 \r
 240         Before calling Movenode():\r
 241         source == {1, 2, 3}\r
 242         dest == {1, 2, 3}\r
 243 \r
 244         Affter calling Movenode():\r
 245         source == {2, 3}\r
 246         dest == {1, 1, 2, 3} */\r
 247 void Movenode(struct node** destRef, struct node** sourceRef)\r
 248 {\r
 249         /* the front source node  */\r
 250         struct node* newnode = *sourceRef;\r
 251         assert(newnode != NULL);\r
 252 \r
 253         /* Advance the source pointer */\r
 254         *sourceRef = newnode->next;\r
 255 \r
 256         /* Link the old dest off the new node */\r
 257         newnode->next = *destRef;\r
 258 \r
 259         /* Move dest to point to the new node */\r
 260         *destRef = newnode;\r
 261 }\r
 262 \r
 263 /*      Function to insert a node at the beginging of the\r
 264         linked list */\r
 265 void pushll(struct node** head_ref, int new_data)\r
 266 {\r
 267         /* allocate node */\r
 268         struct node* new_node =\r
 269                 (struct node*) malloc(sizeof(struct node));\r
 270 \r
 271         /* put in the data  */\r
 272         new_node->data = new_data;\r
 273 \r
 274         /* link the old list off the new node */\r
 275         new_node->next = (*head_ref);\r
 276 \r
 277         /* move the head to point to the new node */\r
 278         (*head_ref)     = new_node;\r
 279 }\r
 280 \r
 281 /* Function to print nodes in a given linked list */\r
 282 void printList(struct node *node)\r
 283 {\r
 284         while (node!=NULL)\r
 285         {\r
 286                 printf("%d ", node->data);\r
 287                 node = node->next;\r
 288         }\r
 289 }\r
 290 #endif\r