You have two singly linked lists that are already sorted, you have to merge them

Question

You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as wel

Explanation / Answer

// Insert a new node in a sorted list int sortedInsert(struct ListNode **head, struct ListNode* newNode) { int headUpdated = 0; struct ListNode *current; // The list is empty or the new element has to be added as first element if (*head == NULL || (*head)->data >= newNode->data) { newNode->next = *head; *head = newNode; headUpdated = 1; } else { // Locate the node before the point of insertion current = *head; while (current->next != NULL && current->next->data data) current = current->next; newNode->next = current->next; current->next = newNode; } return headUpdated; } struct ListNode *mergeLists(struct ListNode *head1, struct ListNode *head2) { if (head1 == NULL) return head2; if (head2 == NULL) return head1; // Store the node in the first list where to start the comparisons struct ListNode *first = head1; while (head2) { struct ListNode *head2Next = head2->next; printf("Adding %d starting comparison from %d ", head2->data, first->data); if (sortedInsert(&first, head2)) head1 = first; first = head2; head2 = head2Next; } return head1; }

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.