【链表】-Lc21-合并两个有序链表（同时遍历）

写在前面

  最近想复习一下数据结构与算法相关的内容，找一些题来做一做。如有更好思路，欢迎指正。

---

---

一、场景描述

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

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
1
2
3

---

二、具体步骤

1.环境说明

2.代码

以下为Java版本实现：

public class Lc21_mergeTwoLists {

    public static void main(String[] args) {
        ListNode list1n3 = new ListNode(4);
        ListNode list1n2 = new ListNode(2, list1n3);
        ListNode list1Head = new ListNode(1, list1n2);
        ListNode.print(list1Head);

        System.out.println();

        ListNode list2n3 = new ListNode(4);
        ListNode list2n2 = new ListNode(3, list2n3);
        ListNode l2head = new ListNode(1, list2n2);
        ListNode.print(l2head);

        System.out.println();

        ListNode.print(mergeTwoLists(list1Head, l2head));
    }


    /**
     * 约束条件：2个有序链表
     *
     * 思路：
     *
     * 返回值是ListNode
     * 2个有序链表合并，涉及2个数字比较大小，还有长度不一致的问题
     *
     * 定义dummy，curr = dummy
     * while循环（l1 != null && l2!= null），l1并且l2都没有遍历完
     *
     * 比较 l1.val 和 l2.val，并且移动指针
     * l1.val < l2.val, curr.next = l1.val, l1 = l1.next
     * 否则，curr.next = l2.val, l2 = l2.next
     *
     * 循环结束，说明l1、l2至少有一个循环完了，这个时候要处理后面的链
     * curr.next = l1 == null ? l2 : l1;
     *
     * 最后返回dummy.next即head
     *
     * @param l1
     * @param l2
     * @return
     */
    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 定义哑结点
        ListNode dummy = new ListNode();
        ListNode curr = dummy;

        // 循环比较
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                // 此处不需要新建结点
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            // 向后循环一个指针
            curr = curr.next;
        }

        // 链表长度不一致问题
        curr.next = l1 == null ? l2 : l1;

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

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

        static void print(ListNode head) {
            while (head != null) {
                if (head.next == null) {
                    System.out.print(head.val);
                } else {
                    System.out.print(head.val + ", ");
                }

                head = head.next;
            }
        }

    }
}
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

---

写在后面

  如果本文内容对您有价值或者有启发的话，欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。