用java简单且最佳的方式合并两个排序的链表

合并两个排序链表是一个可以有效解决的常见问题。以下是如何使用 Java 以简单且最佳的方式完成此操作。

步骤：

1. 创建虚拟节点：使用虚拟节点来帮助简化合并过程。该节点将作为合并列表的开始。
2. 比较节点：比较两个链表的当前节点。将较小的节点附加到合并列表并将该列表的指针向前移动。
3. 处理剩余节点：如果一个列表先于另一个列表耗尽，则将未耗尽列表的剩余节点附加到合并列表。
4. 返回合并列表：合并列表从虚拟节点旁边的节点开始。

Java实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

解释：

1. ListNode 类:

   • 用一个整数值（val）和一个指向下一个节点（next）的指针来表示链表中的每个节点。

2. mergeTwoLists 方法:

   • 虚拟节点：虚拟节点（dummy）用于通过提供起点来简化合并过程。
   • 比较循环：我们遍历两个链表，比较当前节点。较小的节点将添加到合并列表中，然后我们移动到该列表中的下一个节点。
   • 剩余节点：其中一个列表耗尽后，我们将另一个列表的剩余部分直接附加到合并列表。
   • 返回：最后，合并列表从虚拟节点旁边的节点开始。

3. printList 方法:

   • 此实用函数会打印链接列表中的所有节点，以便于可视化。

4. 主要方法:

   • 创建两个排序链表：例如1 -> 3-> 5和2-> 4-> 6.
   • 合并列表：合并后的列表将为 1 -> 2-> 3-> 4-> 5-> 6.
   • 打印列表：合并前后查看效果。

复杂：

• 时间复杂度： ( O(n + m) )，其中 ( n ) 和 ( m ) 是两个链表的长度。两个列表中的每个节点都只处理一次。
• 空间复杂度：( O(1) )，因为除了几个指针之外没有使用额外的空间。

此方法既简单又适合合并两个排序的链表，确保代码高效且干净。

以上是用java简单且最佳的方式合并两个排序的链表的详细内容。更多信息请关注PHP中文网其他相关文章！