题解 | #合并两个排序的链表#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //创建一个虚节点,用于最后结果输出 ListNode pre = new ListNode(-1); ListNode res = pre; //两个链表合并,首先想到是双指针 //定义list1, list2的指针分别是 p1,p2 ListNode p1 = list1; ListNode p2 = list2; if(list1!=null&&list2==null) return list1; else if(list1==null&&list2!=null) return list2; else if(list1==null&&list2==null) return null; //遍历list1, list2 while(p1!=null && p2!=null){ //当list的值小时, if(p1.val < p2.val){ //将此值(这里是list1)加到pre后 pre.next = p1; //pre前移 pre = pre.next; //p1前移 p1 = p1.next; //当list1已经移动完毕,则需要将list2剩下的节点全部加到尾部即可 if(p1==null){ pre.next = p2; } }else if(p1.val > p2.val){ pre.next = p2; pre = pre.next; p2 = p2.next; if(p2==null){ pre.next = p1; } }else{ pre.next =p1; p1 = p1.next; pre = pre.next; pre.next =p2; p2 = p2.next; pre = pre.next; } } return res.next; } }
双指针比较两个链表,依次找出小的节点,将找出的节点放到新的链表中。
如果遇到相同的值,则依次加到新的链表中。