#include "src/lib/ll.h"\r
\r
+#ifdef OTHERMERGELISTSTIFF\r
+int listLength(node_t * item)\r
+{\r
+ node_t * cur = item;\r
+ int size = 0;\r
+\r
+ while (cur->next != NULL)\r
+ {\r
+ ++size;\r
+ cur = cur->next;\r
+ }\r
+\r
+ return size;\r
+}\r
+\r
void print_list(node_t * head)\r
{\r
node_t * current = head;\r
\r
- while (current != NULL)\r
+ while (current->next != NULL)\r
{\r
- printf("[%u] %d\n", current->id, current->val);\r
+ printf("[%u]= %d\n", current->id, current->val);\r
current = current->next;\r
}\r
}\r
\r
return retval;\r
}\r
+#else\r
+/* Takes two lists sorted in increasing order, and splices\r
+ their nodes together to make one big sorted list which\r
+ is returned. */\r
+struct node* SortedMerge(struct node* a, struct node* b)\r
+{\r
+ /* a dummy first node to hang the result on */\r
+ struct node dummy;\r
+\r
+ /* tail points to the last result node */\r
+ struct node* tail = &dummy;\r
+\r
+ /* so tail->next is the place to add new nodes\r
+ to the result. */\r
+ dummy.next = NULL;\r
+ while (1)\r
+ {\r
+ if (a == NULL)\r
+ {\r
+ /* if either list runs out, use the\r
+ other list */\r
+ tail->next = b;\r
+ break;\r
+ }\r
+ else if (b == NULL)\r
+ {\r
+ tail->next = a;\r
+ break;\r
+ }\r
+ if (a->data <= b->data)\r
+ Movenode(&(tail->next), &a);\r
+ else\r
+ Movenode(&(tail->next), &b);\r
+\r
+ tail = tail->next;\r
+ }\r
+ return(dummy.next);\r
+}\r
+\r
+struct node* LL_merge(struct node* a, struct node* b)\r
+{\r
+ /* a dummy first node to hang the result on */\r
+ struct node dummy;\r
+\r
+ /* tail points to the last result node */\r
+ struct node* tail = &dummy;\r
+\r
+ /* so tail->next is the place to add new nodes\r
+ to the result. */\r
+ dummy.next = NULL;\r
+ Movenode(&(tail->next), &a);\r
+ a = a->next;\r
+ tail = tail->next;\r
+ while (1)\r
+ {\r
+ if (a == NULL)\r
+ {\r
+ /* if either list runs out, use the\r
+ other list */\r
+ tail->next = b;\r
+ break;\r
+ }\r
+ else if (b == NULL)\r
+ {\r
+ tail->next = a;\r
+ break;\r
+ }\r
+ if (a->data <= b->data)\r
+ Movenode(&(tail->next), &a);\r
+ else\r
+ Movenode(&(tail->next), &b);\r
+\r
+ tail = tail->next;\r
+ }\r
+ return(dummy.next);\r
+}\r
+\r
+/* The function removes duplicates from a sorted list */\r
+void removeDuplicates(struct node* head)\r
+{\r
+ /* Pointer to traverse the linked list */\r
+ struct node* current = head;\r
+ \r
+ /* Pointer to store the next pointer of a node to be deleted*/\r
+ struct node* next_next;\r
+\r
+ /* do nothing if the list is empty */\r
+ if (current == NULL)\r
+ return;\r
+ \r
+ /* Traverse the list till last node */\r
+ while (current->next != NULL)\r
+ {\r
+ /* Compare current node with next node */\r
+ if (current->data == current->next->data)\r
+ {\r
+ /* The sequence of steps is important */\r
+ next_next = current->next->next;\r
+ free(current->next);\r
+ current->next = next_next;\r
+ }\r
+ else /* This is tricky: only advance if no deletion */\r
+ {\r
+ current = current->next;\r
+ }\r
+ }\r
+}\r
+\r
+/* UTILITY FUNCTIONS */\r
+/* Movenode() function takes the node from the front of the\r
+ source, and move it to the front of the dest.\r
+ It is an error to call this with the source list empty.\r
+\r
+ Before calling Movenode():\r
+ source == {1, 2, 3}\r
+ dest == {1, 2, 3}\r
+\r
+ Affter calling Movenode():\r
+ source == {2, 3}\r
+ dest == {1, 1, 2, 3} */\r
+void Movenode(struct node** destRef, struct node** sourceRef)\r
+{\r
+ /* the front source node */\r
+ struct node* newnode = *sourceRef;\r
+ assert(newnode != NULL);\r
+\r
+ /* Advance the source pointer */\r
+ *sourceRef = newnode->next;\r
+\r
+ /* Link the old dest off the new node */\r
+ newnode->next = *destRef;\r
+\r
+ /* Move dest to point to the new node */\r
+ *destRef = newnode;\r
+}\r
+#endif\r
+\r
+/* Function to insert a node at the beginging of the\r
+ linked list */\r
+void pushll(struct node** head_ref, int new_data)\r
+{\r
+ /* allocate node */\r
+ struct node* new_node =\r
+ (struct node*) malloc(sizeof(struct node));\r
+\r
+ /* put in the data */\r
+ new_node->data = new_data;\r
+\r
+ /* link the old list off the new node */\r
+ new_node->next = (*head_ref);\r
+\r
+ /* move the head to point to the new node */\r
+ (*head_ref) = new_node;\r
+}\r
+\r
+/* Function to print nodes in a given linked list */\r
+void printList(struct node *node)\r
+{\r
+ while (node!=NULL)\r
+ {\r
+ printf("%d ", node->data);\r
+ node = node->next;\r
+ }\r
+}\r
+#endif\r
projects / 16.git / blobdiff