2025年- H32-Lc140 --21. 合并两个有序链表--Java版

1.题目描述

2.思路

(1)定义一个虚拟的头节点，然后pre指针刚开始赋值要等于这个虚拟头节点
(2)比较l1和l2值得大小，如果l1小，就把指针指向l1（pre.next=l1），同时list指针要向后移list1=list1.next；如果l2小，就把指针指向l2（pre.next=l2）；
(3) 指针后移pre=pre.next;
(4)如果链表的大小不一样。比如l1null，说明l2还有元素，把此时的pre指针指向l2，比如pre.next=l2。比如l2null，说明l1还有元素，把此时的pre指针指向l1，比如pre.next=l1。

3.代码实现

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;}
}
public class H21 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//1.创建一个虚拟头节点,虚拟头节点这边可以是任意值ListNode dummyhead=new ListNode(-1);//2.设置一个pre指针，刚开始从在虚拟头节点上ListNode pre=dummyhead;//3.因为是两个有序链表合并，最后组合成一个有序链表//循环终止条件是list1=null和list2=null就停止变量while(list1!=null&&list2!=null){//4.开始比较两个链表的值if(list1.val<=list2.val){pre.next=list1;//因为list1的值比较小，所以pre的next指针直接指向list1list1=list1.next;//继续移动list1的指针}else{pre.next=list2;list2=list2.next;//继续移动list2的指针}//5.比较完list1和list2的大小之后，pre指针要继续后移(在新组成整个链上移动）。pre=pre.next;}//4. 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可if(list1==null)//l1为空，但是l2还有值{pre.next=list2;//将此时l1尾部pre指针指向list2的剩余节点}else{pre.next=list1;}return dummyhead.next;}public static void main(String[] args){H21 test=new H21();//创建第一个链表并且赋值ListNode node3=new ListNode(4,null);ListNode node2=new ListNode(2,node3);ListNode head=new ListNode(1,node2);//创建第二个链表并且赋值ListNode node3_l2=new ListNode(3,null);ListNode node2_l2=new ListNode(2,node3_l2);ListNode head_l2=new ListNode(1,node2_l2);ListNode res=test.mergeTwoLists(head,head_l2);System.out.print("输出合并两个有序链表的结果:");while(res!=null){System.out.print(res.val);if(res.next!=null){System.out.print("->");}//res要继续往后移res=res.next;}}}