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

Опубликовано: 21 Января, 2022

Нам дается два отсортированных списка, и наша цель - объединить эти два списка в новый список. Для этого мы должны написать одну функцию, которая будет принимать два списка в качестве аргумента, которые сортируются в порядке возрастания. Эта функция объединит эти два списка в один список в порядке возрастания.

 Вход
Список 1: 1-> 3-> 4-> 9-> 10
Список 2: 2-> 5-> 6-> 9

Выход
Новый список: 1-> 2-> 3-> 4-> 5-> 6-> 9-> 9-> 10

У нас есть два подхода к решению этой проблемы:

Итеративный
Рекурсивный

Метод 1: итерационный подход

Идея этого подхода заключается в том, что мы возьмем один дополнительный узел в новом списке, который является головным узлом списка.
Мы возьмем одну переменную из списка типов, которая всегда находится в последнем узле списка, чтобы упростить добавление нового узла.
Мы будем повторять цикл и проверять наличие меньшего элемента из обоих списков и добавлять этот узел в результирующий список.
Если мы достигли конца любого списка, мы просто добавим оставшиеся узлы из второго списка.

Implementation:

Java

// Java Program to Merge Two Sorted
// Linked Lists in New List
// Iteratively
  
import java.io.*;
  
public class ListNode {
  
    int val;
    ListNode next;
  
    ListNode() {}
    ListNode(int val) { this.val = val; }
  
    ListNode(int val, ListNode next)
    {
        this.val = val;
        this.next = next;
    }
}
  
class GFG {
    public static ListNode mergeTwoLists(ListNode l1,
                                         ListNode l2)
    {
        // New List
        ListNode result = new ListNode(-1);
  
        // variable to point the last node of the list.
        ListNode p = result;
  
        // Iterate the loop
        while (l1 != null && l2 != null) {
            // Find the smaller element and append it to the
            // list.
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            }
  
            else {
                p.next = l2;
                l2 = l2.next;
            }
  
            // Update the variable
            p = p.next;
        }
  
        // If anyone list become empty append the remaining
        // list element of othe list.
        if (l1 == null) {
            p.next = l2;
        }
  
        else if (l2 == null) {
            p.next = l1;
        }
  
        // Return the resultant list without first extra
        // node
        return result.next;
    }
  
    // A utility function to print linked list
    static void printList(ListNode node)
    {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);
  
        // 1->3->5 LinkedList created
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(4);
  
        // 0->2->4 LinkedList created
        ListNode mergedhead = mergeTwoLists(head1, head2);
  
        printList(mergedhead);
    }
}

Output

0 1 2 3 4 5

Picked Java

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

Java

РЕКОМЕНДУЕМЫЕ СТАТЬИ