package com.thealgorithms.datastructures.lists;

/**
 * Utility class for merging two sorted singly linked lists.
 *
 * <p>This class extends the {@link SinglyLinkedList} class to support the merging of two sorted linked lists.
 * It provides a static method, `merge`, that takes two sorted singly linked lists, merges them into a single sorted linked list,
 * and returns the result.</p>
 *
 * <p>Example usage:</p>
 * <pre>
 * SinglyLinkedList listA = new SinglyLinkedList();
 * SinglyLinkedList listB = new SinglyLinkedList();
 * for (int i = 2; i <= 10; i += 2) {
 *     listA.insert(i);   // listA: 2->4->6->8->10
 *     listB.insert(i - 1); // listB: 1->3->5->7->9
 * }
 * SinglyLinkedList mergedList = MergeSortedSinglyLinkedList.merge(listA, listB);
 * System.out.println(mergedList); // Output: 1->2->3->4->5->6->7->8->9->10
 * </pre>
 *
 * <p>The `merge` method assumes that both input lists are already sorted in ascending order.
 * It returns a new singly linked list that contains all elements from both lists in sorted order.</p>
 *
 * @see SinglyLinkedList
 */
public class MergeSortedSinglyLinkedList extends SinglyLinkedList {

    /**
     * Merges two sorted singly linked lists into a single sorted singly linked list.
     *
     * <p>This method does not modify the input lists; instead, it creates a new merged linked list
     * containing all elements from both lists in sorted order.</p>
     *
     * @param listA The first sorted singly linked list.
     * @param listB The second sorted singly linked list.
     * @return A new singly linked list containing all elements from both lists in sorted order.
     * @throws NullPointerException if either input list is null.
     */
    public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) {
        if (listA == null || listB == null) {
            throw new NullPointerException("Input lists must not be null.");
        }

        Node headA = listA.getHead();
        Node headB = listB.getHead();
        int size = listA.size() + listB.size();

        Node head = new Node();
        Node tail = head;
        while (headA != null && headB != null) {
            if (headA.value <= headB.value) {
                tail.next = headA;
                headA = headA.next;
            } else {
                tail.next = headB;
                headB = headB.next;
            }
            tail = tail.next;
        }

        // Attach remaining nodes
        tail.next = (headA == null) ? headB : headA;

        return new SinglyLinkedList(head.next, size);
    }
}