5.合并两个有序链表

链表合并

B站左程云讲解连接

链表结构

public static class ListNode {
        public int val;
        public ListNode next;

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

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

合并方法

class Solution {
        public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
            if (head1 == null || head2 == null) {
                return head1 == null ? head2 : head1;//如果head1 == null则返回head2，否则返回head1
            }
            //将新链表的头节点指向原先两个链表中头节点较小的链表的第一个元素
            ListNode head = head1.val <= head2.val ? head1 : head2;
            //cur1指向新链表头节点所在链表的下一个节点
            ListNode cur1 = head.next;
            //cur2指向另一个链表的toujeid
            ListNode cur2 = head == head1 ? head2 : head1;
            //初始化指向新链表的头节点，在后续过程pre.next总指向新链表中下一个添加的节点,并在添加一个节点后移动至新添加的节点位置
            ListNode pre = head;

            while (cur1 != null && cur2 != null) {
                if (cur1.val <= cur2.val) {
                    pre.next = cur1;
                    cur1 = cur1.next;
                }else {
                    pre.next = cur2;
                    cur2 = cur2.next;
                }
                 pre = pre.next;//移动至刚添加进新链表的节点位置

            }
            pre.next = cur1==null?cur2:cur1;//如果cu1为null则将cur2余下部分merge后边，否则将cur1余下部分拼接后边
            return head;
        }
    }

对应测试链接