博客

思路：

创建一个新链表，将排好序的节点一一加入

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode node=new ListNode(0);
		ListNode hair=node;
		ListNode p1=l1,p2=l2;
		
		while(p1!=null&&p2!=null){
			if(p1.val<=p2.val){
				hair.next=p1;
				p1=p1.next;
			}
			else{
				hair.next=p2;
				p2=p2.next;
			}
			hair=hair.next;
		}
		
		hair.next=p1==null?p2:p1;
		return node.next;
    }
}

分解：

1）创建一个节点node和一个指向该节点的指针，指针用于加入，node用于返回最终结果

2）为2个链表也分别创建一个指针

3）最后用一个三元表达式将剩下的不为null的部分全部加入到链表中，同一个链表中剩下的部分都是排好序的

hair.next=p1==null?p2:p1;

复杂度分析：

时间复杂度：O（N）需要遍历N个节点

空间复杂度：O（N）额外创建了一个N个节点的链表

第一次就完整写出来通过啦！！