Повторно объединить и отсортировать два связанных списка в третий в обратном порядке

Question

Я пытаюсь написать единственную функцию в Java (Node sortedmerge(Node node1, Node node2)), где данные в node1 и node2 уже отсортированы в порядке убывания ({5, 3, 1, 0}). Я придумал реализацию функции, но не могу понять, как сделать ее рекурсивной:

//Defined elsewhere as a global variable
static Node<Integer> head = new Node();
//Used to store the final sorted linked list

Node sortedmerge(Node node1, Node node2) {

    // if both the nodes are null
    if (node1 == null && node2 == null) {
        return null;
    }

    // if both of them have nodes present traverse them
    while (node1 != null && node2 != null) {

        // Now compare both nodes current data
        if (node1.data <= node2.data) {
            Node temp = node1.next;
            node1.next = head;
            head = node1;
            node1 = temp;
        } else {
            Node temp = node2.next;
            node2.next = head;
            head = node2;
            node2 = temp;
        }
    }

    // If second list reached end, but first list has
    // nodes. Add remaining nodes of first list at the
    // front of result list
    while (node1 != null) {
        Node temp = node1.next;
        node1.next = head;
        head = node1;
        node1 = temp;
    }

    // If first list reached end, but second list has
    // node. Add remaining nodes of first list at the
    // front of result list
    while (node2 != null) {
        Node temp = node2.next;
        node2.next = head;
        head = node2;
        node2 = temp;
    }
    return head;
}

предположительно есть способ сделать это без временного узла (Node temp) или любых внешних функций ... но на этом этапе я был бы рад заставить его работать рекурсивно (я изо всех сил пытаюсь понять, как реализовать рекурсивные вызовы).

Answer 1

Ваша функция объединяет два отсортированных списка, вы можете реализовать это с помощью al oop как опубликовано или рекурсивно, как будет показано ниже. Однако учтите, что:

• нет причин делать head глобальной переменной. Вместо этого вы должны определить его как локальный и вернуть как возвращаемое значение функции.
• head в вашем коде указывает не на заголовок списка, а на последний элемент, также известный как хвост node.
• как только один из списков исчерпан, вы можете просто добавить другой к последнему элементу объединенного списка.
• рекурсивная реализация sortedmerge потребует места в стеке, пропорционального длина объединенного списка, которая может легко превышать доступное пространство стека, вызывая переполнение стека исключение.

Вот простая рекурсивная реализация:

Node sortedmerge(Node node1, Node node2) {

    // if either node is null, return the other node
    if (node1 == null) {
        return node2;
    }
    if (node2 == null) {
        return node1;
    }

    // select the node with the largest data
    if (node1.data <= node2.data) {
        // select node2 and append the rest of the merged list to it
        node2.next = sortedmerge(node1, node2.next);
        return node2;
    } else {
        // select node1 and append the rest of the merged list to it
        node1.next = sortedmerge(node1.next, node2);
        return node1;
    }
}