Java算法_合并两个排序列(LeetCode_Hot100)

题目描述：题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

获得更多？算法思路:代码文档，算法解析的私得。

运行效果

完整代码

import java.util.List;

/**
 * 2 * @Author: LJJ
 * 3 * @Date: 2023/8/3 10:43
 * 4
 */
public class MergeTwoSortedLists {

    static class ListNode{
        int val;
        ListNode next;

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

    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode newHead = new ListNode(0); // 新链表头节点
        ListNode newCurrent = newHead;  // 新链表当前节点

        ListNode p1 = l1;   // 指向链表 l1 的指针
        ListNode p2 = l2;   // 指向链表 l2 的指针

        // 比较 l1 和 l2 中的节点值，并将较小的节点添加到新链表中
        while (p1 !=null && p2 !=null){
            if (p1.val <= p2.val){
                newCurrent.next = p1;
                p1 = p1.next;
            }else {
                newCurrent.next = p2;
                p2 = p2.next;
            }
            newCurrent = newCurrent.next;

        }
        // 将 l1 或 l2 中剩余的节点添加到新链表中
        if (p1 !=null){
            newCurrent.next = p1;
        }
        if (p2 !=null){
            newCurrent.next = p2;
        }
        return newHead.next; // 返回新链表的头节点，即合并后的结果
    }
    // 打印链表的函数
    private static void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        // 创建第一个链表: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // 创建第二个链表: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        // 输出合并前的链表 l1 和 l2
        System.out.println("合并前的链表 l1:");
        printLinkedList(l1);

        System.out.println("合并前的链表 l2:");
        printLinkedList(l2);

        // 创建 MergeTwoSortedLists 对象，调用 mergeTwoLists 方法进行链表合并
        MergeTwoSortedLists merger = new MergeTwoSortedLists();
        ListNode mergedList = merger.mergeTwoLists(l1, l2);

        // 输出合并后的链表
        System.out.println("合并后的链表:");
        printLinkedList(mergedList);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84