-#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->next != NULL)\r
- {\r
- printf("[%u]= %d\n", current->id, current->val);\r
- current = current->next;\r
- }\r
-}\r
-\r
-void pushe(node_t * head, int val)\r
-{\r
- node_t * current = head;\r
- current->id = head->id;\r
- current->next->id = current->id+1;\r
-\r
- while (current->next != NULL)\r
- {\r
- current->next->id = current->id;\r
- current = current->next;\r
- current->id++;\r
- }\r
-\r
- // now we can add a new variable\r
- current->next = malloc(sizeof(node_t));\r
- current->next->val = val;\r
- current->next->next = NULL;\r
- current->next->id++;\r
-}\r
-\r
-void pushs(node_t ** head, int val)\r
-{\r
- node_t * new_node;\r
- new_node = malloc(sizeof(node_t));\r
-\r
- new_node->val = val;\r
- new_node->next = *head;\r
- *head = new_node;\r
-}\r
-\r
-int pop(node_t ** head)\r
-{\r
- int retval = -1;\r
- node_t * next_node = NULL;\r
-\r
- if (*head == NULL) {\r
- return -1;\r
- }\r
-\r
- next_node = (*head)->next;\r
- retval = (*head)->val;\r
- free(*head);\r
- *head = next_node;\r
-\r
- return retval;\r
-}\r
-\r
-int remove_last(node_t * head)\r
-{\r
- int retval = 0;\r
- node_t * current;\r
-\r
- /* if there is only one item in the list, remove it */\r
- if (head->next == NULL) {\r
- retval = head->val;\r
- free(head);\r
- return retval;\r
- }\r
-\r
- /* get to the last node in the list */\r
- current = head;\r
- while (current->next->next != NULL) {\r
- current = current->next;\r
- }\r
-\r
- /* now current points to the last item of the list, so let's remove current->next */\r
- retval = current->next->val;\r
- free(current->next);\r
- current->next = NULL;\r
- return retval;\r
-\r
-}\r
-\r
-int remove_by_index(node_t ** head, int n)\r
-{\r
- int i = 0;\r
- int retval = -1;\r
- node_t * current = *head;\r
- node_t * temp_node = NULL;\r
-\r
- if (n == 0) {\r
- return pop(head);\r
- }\r
-\r
- for (i = 0; i < n-1; i++) {\r
- if (current->next == NULL) {\r
- return -1;\r
- }\r
- current = current->next;\r
- }\r
-\r
- temp_node = current->next;\r
- retval = temp_node->val;\r
- current->next = temp_node->next;\r
- free(temp_node);\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
-\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
OSDN Git Service
