1 #include "src/lib/ll.h"
\r
3 #ifdef OTHERMERGELISTSTIFF
\r
4 int listLength(node_t * item)
\r
9 while (cur->next != NULL)
\r
18 void print_list(node_t * head)
\r
20 node_t * current = head;
\r
22 while (current->next != NULL)
\r
24 printf("[%u]= %d\n", current->id, current->val);
\r
25 current = current->next;
\r
29 void pushe(node_t * head, int val)
\r
31 node_t * current = head;
\r
32 current->id = head->id;
\r
33 current->next->id = current->id+1;
\r
35 while (current->next != NULL)
\r
37 current->next->id = current->id;
\r
38 current = current->next;
\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
49 void pushs(node_t ** head, int val)
\r
52 new_node = malloc(sizeof(node_t));
\r
54 new_node->val = val;
\r
55 new_node->next = *head;
\r
59 int pop(node_t ** head)
\r
62 node_t * next_node = NULL;
\r
64 if (*head == NULL) {
\r
68 next_node = (*head)->next;
\r
69 retval = (*head)->val;
\r
76 int remove_last(node_t * head)
\r
81 /* if there is only one item in the list, remove it */
\r
82 if (head->next == NULL) {
\r
88 /* get to the last node in the list */
\r
90 while (current->next->next != NULL) {
\r
91 current = current->next;
\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
102 int remove_by_index(node_t ** head, int n)
\r
106 node_t * current = *head;
\r
107 node_t * temp_node = NULL;
\r
113 for (i = 0; i < n-1; i++) {
\r
114 if (current->next == NULL) {
\r
117 current = current->next;
\r
120 temp_node = current->next;
\r
121 retval = temp_node->val;
\r
122 current->next = temp_node->next;
\r
128 /* Takes two lists sorted in increasing order, and splices
\r
129 their nodes together to make one big sorted list which
\r
131 struct node* SortedMerge(struct node* a, struct node* b)
\r
133 /* a dummy first node to hang the result on */
\r
136 /* tail points to the last result node */
\r
137 struct node* tail = &dummy;
\r
139 /* so tail->next is the place to add new nodes
\r
146 /* if either list runs out, use the
\r
151 else if (b == NULL)
\r
156 if (a->data <= b->data)
\r
157 Movenode(&(tail->next), &a);
\r
159 Movenode(&(tail->next), &b);
\r
163 return(dummy.next);
\r
166 struct node* LL_merge(struct node* a, struct node* b)
\r
168 /* a dummy first node to hang the result on */
\r
171 /* tail points to the last result node */
\r
172 struct node* tail = &dummy;
\r
174 /* so tail->next is the place to add new nodes
\r
177 Movenode(&(tail->next), &a);
\r
184 /* if either list runs out, use the
\r
189 else if (b == NULL)
\r
194 if (a->data <= b->data)
\r
195 Movenode(&(tail->next), &a);
\r
197 Movenode(&(tail->next), &b);
\r
201 return(dummy.next);
\r
204 /* The function removes duplicates from a sorted list */
\r
205 void removeDuplicates(struct node* head)
\r
207 /* Pointer to traverse the linked list */
\r
208 struct node* current = head;
\r
210 /* Pointer to store the next pointer of a node to be deleted*/
\r
211 struct node* next_next;
\r
213 /* do nothing if the list is empty */
\r
214 if (current == NULL)
\r
217 /* Traverse the list till last node */
\r
218 while (current->next != NULL)
\r
220 /* Compare current node with next node */
\r
221 if (current->data == current->next->data)
\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
228 else /* This is tricky: only advance if no deletion */
\r
230 current = current->next;
\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
240 Before calling Movenode():
\r
241 source == {1, 2, 3}
\r
244 Affter calling Movenode():
\r
246 dest == {1, 1, 2, 3} */
\r
247 void Movenode(struct node** destRef, struct node** sourceRef)
\r
249 /* the front source node */
\r
250 struct node* newnode = *sourceRef;
\r
251 assert(newnode != NULL);
\r
253 /* Advance the source pointer */
\r
254 *sourceRef = newnode->next;
\r
256 /* Link the old dest off the new node */
\r
257 newnode->next = *destRef;
\r
259 /* Move dest to point to the new node */
\r
260 *destRef = newnode;
\r
263 /* Function to insert a node at the beginging of the
\r
265 void pushll(struct node** head_ref, int new_data)
\r
267 /* allocate node */
\r
268 struct node* new_node =
\r
269 (struct node*) malloc(sizeof(struct node));
\r
271 /* put in the data */
\r
272 new_node->data = new_data;
\r
274 /* link the old list off the new node */
\r
275 new_node->next = (*head_ref);
\r
277 /* move the head to point to the new node */
\r
278 (*head_ref) = new_node;
\r
281 /* Function to print nodes in a given linked list */
\r
282 void printList(struct node *node)
\r
286 printf("%d ", node->data);
\r