合并k个已排序的链表

 // 思路1: 使用优先队列(实质与堆相差无几)  priority_queue
   /*
   struct compare
    {
      bool operator()(const ListNode* l, const ListNode* r)
        {
            return l->val > r->val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) 
    { 
       priority_queue<ListNode *, vector<ListNode *>,compare> q;  //compare
       for(auto l:lists)
         if(l)  q.push(l);
       if(q.empty())  return NULL;
        ListNode fake(0);
        ListNode *result = &fake;
        while(!q.empty())
        {
            result->next = q.top();
            q.pop();
            result = result->next;
            if(result->next)
                q.push(result->next);
        }
        return fake.next;
    }
    */
    // 思路2：使用堆（默认最大堆，改成最小堆，链表依次加入最小堆弹出节点，加入该节点所在链表新节点，不断调整堆......STL中提供heap算法
    
   
    static bool compareLess(ListNode* l1,ListNode* l2)
    {
        return l1->val > l2->val;
    }
    ListNode* mergeKLists(vector<ListNode*> &lists) 
    {
       ListNode fake(0);
       ListNode *cur = &fake;
       vector<ListNode *> vec;
       
       int listSize = lists.size();
       for(int i=0;i<listSize;i++)
       {
           if(lists[i])
                vec.push_back(lists[i]);
       }
       make_heap(vec.begin(),vec.end(),compareLess);      // 建堆
       while(vec.size())
       {
           cur->next = vec.front();                       // 堆第一个节点first为最小值节点
           pop_heap(vec.begin(),vec.end(),compareLess);   // 它把first和last-1交换，然后重新生成一个堆
           vec.pop_back();                                // 容器弹出最后一个节点
           cur = cur->next;
           if(cur->next)                                  // 添加弹出的最小值的节点所在链表节点 last-1位置
           {
               vec.push_back(cur->next);                 
               push_heap(vec.begin(),vec.end(),compareLess);  // first到last-1是一个有效堆，新加入元素重新生成堆
           }
       }
       return fake.next;
     }
     
     
      // 思路3：分治算法，基于两个排序链表的合并，两两合并后继续合并，每一轮复杂度o(n),n为总节点个数，T(n) = 2T(n/2) + o(n),迭代次数为lg(k),因此复杂度为o(nlgk)
       /* 
       ListNode* mergeTwoSortedLists(ListNode* L1,ListNode* L2)
      {
          if(L1== nullptr)
            return L2;
          if(L2==nullptr)
            return L1;
          if(L1->val <= L2->val)
          {
              L1->next = mergeTwoSortedLists(L1->next,L2);
              return L1;
          }
          else
          {
              L2->next = mergeTwoSortedLists(L1,L2->next);
              return L2;
          }
      }
   
     ListNode* mergeKLists(vector<ListNode*> &lists) 
      {
          if(lists.empty())
            return nullptr;
          while(lists.size()>1)
          {
              lists.push_back(mergeTwoSortedLists(lists[0],lists[1]));
              lists.erase(lists.begin());
              lists.erase(lists.begin());
          }
          return lists.front();
      }
      */

import java.util.*;


public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0)
            return null;

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val)
                    return -1;
                else if (o1.val == o2.val)
                    return 0;
                else
                    return 1;
            }
        });

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        for (ListNode node : lists)
            if (node != null)
                queue.add(node);

        while (!queue.isEmpty()) {
            tail.next = queue.poll();
            tail = tail.next;

            if (tail.next != null)
                queue.add(tail.next);
        }
        return dummy.next;
    }
}

ListNode *mergeKLists(vector<ListNode *> &lists) {
    vector <int> vec;
    if (lists.size() == 0)
        return NULL;
    for (int i = 0; i < lists.size(); ++i)
    {
        ListNode *p = lists[i];
        while (p)
        {
            vec.push_back(p->val);
            p = p->next;
        }
    }
    sort(vec.begin(), vec.end());
    if (vec.size() == 0)
        return NULL;
    ListNode *head = new ListNode(vec[0]);
    ListNode *p = head;
    for (int i = 1; i < vec.size(); ++i)
    {
        p->next = new ListNode(vec[i]);
        p = p->next;
    }
    return head;
}

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
		if(lists.size() == 0) return null;
		ListNode head = lists.get(0);
		for (int i = 1; i < lists.size(); i ++ )
			head = merge2Lists(head, lists.get(i));
		return head;
	}

	public static ListNode merge2Lists(ListNode head1, ListNode head2) {
		ListNode dummy = new ListNode(0), p = dummy;
		while (head1 != null && head2 != null) {
			if(head1.val < head2.val) {
				p.next = head1;
				head1 = head1.next;
			} else {
				p.next = head2;
				head2 = head2.next;
			}
			p = p.next;
		}
		p.next = (head1 == null) ? head2 : head1;
		return dummy.next;
	}
}

归并排序算法的时间复杂度是o(nlogn)
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
       if(lists==null||lists.size()==0){
           return null;
       }
       return mergeKList(lists,0,lists.size()-1);
    }
    public ListNode mergeKList(ArrayList<ListNode> lists,int lo,int hi){
        if (hi<=lo) return lists.get(lo);
        int mid=lo+(hi-lo)/2;
        ListNode left = mergeKList(lists,lo,mid);
        ListNode right = mergeKList(lists,mid+1,hi);
        return merge(left,right);
    }
    public ListNode merge(ListNode left,ListNode right){
        ListNode h = new ListNode(-1);
        ListNode tmp=h;
        while(left!=null&&right!=null){
            if(left.val<right.val){
   		tmp.next=left;
                //tmp=tmp.next;
                left=left.next;
            }else{
                tmp.next=right;
               // tmp=tmp.next;
                right=right.next;
            } tmp=tmp.next; }
        if(left!=null){
           
            tmp.next=left;
        }
        if(right!=null){
            tmp.next=right;
        }
        return h.next;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    ListNode* mergeTwoLists(ListNode *l1,ListNode *l2){
        ListNode *cur1=l1;
        ListNode *cur2=l2;
        ListNode *newHead=new ListNode(0);
        ListNode *cur=newHead;
        
        while(cur1!=NULL &&cur2!=NULL){
            if(cur1->val<cur2->val){
                cur->next=cur1;
                cur1=cur1->next;
            }
            else{
                cur->next=cur2;
                cur2=cur2->next;
            }
            cur=cur->next;
        }
        cur->next=(cur1==NULL)?cur2:cur1;
        return newHead->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n=lists.size();
        if(n==0) return NULL;
        
        ListNode *res=lists[0];
        for(int i=1;i<n;++i){
            res=mergeTwoLists(res,lists[i]);
        }
        return res;
    }
};

class Solution {
public:
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        //防御
        if (lists.empty()) return NULL;
        //初始化优先队列，空出第一个位置
        a.resize(lists.size()+1, NULL);
        n = 0;
        for (int i=0; i<lists.size(); i++)
            push(lists[i]);
        //开始遍历所有的已排序链表，直到队列为空
        ListNode *head = NULL, *tail = NULL;
        while(n >= 1){
            //出队
            ListNode* pNode = pop();
            //加到新的链表中
            if(head == NULL){
                head = new ListNode(pNode->val);
                tail = head;
            }
            else
                addNode(tail, pNode->val);
            //加入出队的后继结点
            push(pNode->next);
        }
		return head;
    }
    
    vector<ListNode*> a;
    int n;
    void addNode(ListNode* &p, int v){
        ListNode* q = new ListNode(v);
        p->next = q;
        p = q;
    }
    void swap(int l, int m){
        ListNode* temp = a[l];
        a[l] = a[m];
        a[m] = temp;
    }
    void swim(int k){
        while(k>1 && a[k]->val < a[k/2]->val){//是子结点，并且小于父节点
        	swap(k, k/2);
            k = k/2;
        }
    }
    void sink(int k){
        //只要有子结点
        while (2*k <= n){
            int j = 2*k;
			//找到较小的子结点
            if(j<n && a[j]->val > a[j+1]->val)	j = j+1;
            //如果父结点大于子结点，则交换
			if(a[k]->val > a[j]->val) swap(k, j);
            k = j;
        }
    }
    void push(ListNode* p){
        if (p == NULL)	return;
        //先在最后加入结点，再swim
        a[++n] = p;
        swim(n);
    }
    ListNode* pop(){
        ListNode* retp = a[1];
        swap(1, n--);
        sink(1);
        return retp;
    }
};

思路:两两合并思想
import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size()==0) {
            return null;
        }
        while(lists.size()>1) {
            
            ArrayList<ListNode> newList = new ArrayList<ListNode>();
            for(int i=0;i+1<lists.size();i+=2) {
                ListNode listnode = merge(lists.get(i),lists.get(i+1));
                newList.add(listnode);
            }
            //如果是奇数,将最后一个链表添加到新的集合中
            if(lists.size()%2!=0) {
                newList.add(lists.get(lists.size()-1));
            }
            lists = newList;
        }
        return lists.get(0);
    }
    public ListNode merge(ListNode l1,ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while(l1!=null && l2!=null) {
            if(l1.val<l2.val) {
                p.next = l1;
                p = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                p = l2;
                l2 = l2.next;
            }
        }
        if(l1!=null) {
            p.next = l1;
        }
        if(l2!=null) {
            p.next = l2;
        }
        return dummy.next;
    }
}

ListNode *mergeKLists(vector<ListNode *> &lists) 
    {
        // 用红黑树的K-V结构来存储所有节点，K存的是节点的val，V存的是节点
        // 存好之后就是有序的了
        multimap<int, ListNode*> m1;  

        // 遍历取出所有链表
        for (int i = 0; i < lists.size(); i++)
        {
            // 遍历当前链表的所有节点
            ListNode* cur = lists[i];
            while (cur)
            {
                // 将节点存入红黑树
                m1.insert(make_pair(cur->val, cur));
                cur = cur->next;
            }
        }
        if (m1.size() == 0)  // 树为空表明没有节点存入，直接返回空
        {
            return nullptr;
        }

        // 遍历红黑树，将所有节点连接起来
        ListNode* head = m1.begin()->second;
        ListNode* tail = nullptr;
        for (auto& pair : m1)
        {
            if (tail)
            {
                tail->next = pair.second;
            }
            tail = pair.second;
        }
        return head;
    }

//分治
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)    return NULL;
        return DivideMerge(lists);
    }
    ListNode* DivideMerge(vector<ListNode*>& lists)
    {
        vector<ListNode*> list1;
        vector<ListNode*> list2;
        int count = lists.size();
        for (int i = 0; i < count / 2; i++) {
            list1.push_back(lists[i]);
        }
        for (int i = count / 2; i < count; i++) {
            list2.push_back(lists[i]);
        }
        return MergeList(list1, list2);
    }
    ListNode* MergeList(vector<ListNode*>& list1, vector<ListNode*>& list2)
    {
        if(list1.size() == 1 && list2.size() == 1)
        {
            return Merge(list1[0], list2[0]);
        }
        else if(list1.size() == 1)
        {
            vector<ListNode*> temp;
            temp.push_back(DivideMerge(list2));
            return MergeList(list1, temp);
        }
        else if(list2.size() == 1)
        {
            vector<ListNode*> temp;
            temp.push_back(DivideMerge(list1));
            return MergeList(temp, list2);
        }
        else
        {
            vector<ListNode*> temp1;
            vector<ListNode*> temp2;
            temp1.push_back(DivideMerge(list1));
            temp2.push_back(DivideMerge(list2));
            return MergeList(temp1, temp2);
        }
    }
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL)    return pHead2;
        if (pHead2 == NULL)    return pHead1;

        ListNode* res;
        ListNode* temp;
        if (pHead1->val < pHead2->val) {
            temp = pHead1;
            pHead1 = pHead1->next;
        } else {
            temp = pHead2;
            pHead2 = pHead2->next;
        }
        res = temp;
        while (pHead1 != NULL || pHead2 != NULL) {
            if (pHead1 == NULL) {
                temp->next = pHead2;
                break;
            }
            if (pHead2 == NULL) {
                temp->next = pHead1;
                break;
            }
            if (pHead1->val < pHead2->val) {
                temp->next = pHead1;
                temp = pHead1;
                pHead1 = pHead1->next;
            } else {
                temp->next = pHead2;
                temp = pHead2;
                pHead2 = pHead2->next;
            }
        }
        return res;
    }
};

主要有两个比较好的方法，一个是堆，一个是分治。

js写这个题。如果使用堆(优先队列)的话，难点是需要自己实现堆的数据结构。c或java好像都有内置已经写好的优先队列数据解构。

js利用数组实现堆需要注意的是：

1. push添加元素的时候，向数组尾部添加元素，如果向其他位置添加元素的话(比如数组开头)，会整个打乱堆，需要重新初始化堆。如果向尾部添加元素，只需要重新初始化树的一半就行。
2. 如果要删除开头元素。将开头元素后尾部元素交换后在删除尾部元素。因为直接删除打乱了整个堆的解构，需要重新初始化，而删除尾部元素不会打乱堆，可以只初始化一边。

function mergeKLists( lists ) {
    if (lists.length <= 1) return lists[0] || null;
    let heap = new minHeap(), head = {next: null}, p = head;
    for (let i=0; i<lists.length; ++i) {
        if (lists[i]) {
            heap.push(lists[i]);
        }
    }
    while(heap.heap.length) {
        p.next = heap.pop();
        p = p.next;
        if (p.next) {
             heap.push(p.next);
        }
    }
    return head.next;
}
class minHeap {
    constructor() {
        this.heap = [];
    }
    push(node) {
        this.heap.push(node);
        let i = this.heap.length-1, dad = Math.floor((i-1)/2);
        while(dad >= 0) {
            this.minHeap(dad, i);
            dad = Math.floor((dad-1)/2);
        }
    }
    pop() {
        const i=0, j=this.heap.length-1;
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
        const res = this.heap.splice(j, 1);
        this.minHeap(0, j-1);
        return res[0];
    }
    minHeap(l, r) {
        let dad = l, son = dad*2+1;
        if (son > r) return;
        if (son + 1 <= r && this.heap[son+1].val < this.heap[son].val) {
            ++son;
        }
        if (this.heap[son].val < this.heap[dad].val) {
            [this.heap[dad], this.heap[son]] = [this.heap[son], this.heap[dad]]
            this.minHeap(son, r);
        }
    }
}

分治法：

function mergeKLists( lists ) {
    if (lists.length <= 1) return lists[0] || null;
    return merge(lists, 0, lists.length-1);
}
function merge(lists, l, r) {
    if (l > r) return null;
    if (l === r) return lists[l];
    const mid = Math.floor((l+r)/2);
    return mergeTwoList(merge(lists, l, mid), merge(lists, mid+1, r));
}
function mergeTwoList (list1, list2) {
    if (!list1 || !list2) return list1 || list2;
    let p1 = list1, p2 = list2, head = {next: null}, p = head;
    while(p1 && p2) {
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        p = p.next;
    }
    p.next = p1 || p2;
    return head.next;
}

import java.util.ArrayList;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        if (lists == null || lists.size() == 0){
            return null;
        }
        if (lists.size() == 1){
            return lists.get(0);
        }

        int begin = 0;
        int end = lists.size() - 1;
        while (end>0){
            begin = 0;
            while (begin<end){
                lists.set(begin,mergeTwoLists(lists.get(begin),lists.get(end)));
                begin++;
                end--;
            }
        }

        return lists.get(0);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode mergeNode = null;
        if (l1.val > l2.val) {
            mergeNode = l2;
            mergeNode.next = mergeTwoLists(l1, l2.next);
        } else {
            mergeNode = l1;
            mergeNode.next = mergeTwoLists(l1.next, l2);
        }

        return mergeNode;
    }
}

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
    	ListNode L(0);
    	ListNode *p = &L;
    	vector<ListNode *> v;
    	
    	int n = lists.size();
    	for(int i=0;i<n;i++)
    		if(lists[i] != NULL)
    			v.push_back(lists[i]);
		
		make_heap(v.begin(),v.end(),cmp);
		while(v.size())
		{
			p->next = v.front();
			pop_heap(v.begin(),v.end(),cmp);
			v.pop_back();
			p = p->next;
			if(p->next)
			{
				v.push_back(p->next);
				push_heap(v.begin(),v.end(),cmp);
			}
		}
		return L.next;
    }
    static bool cmp(ListNode *L1,ListNode *L2)
    {
    	return L1->val > L2->val; 
	}
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size()==0)
            return nullptr;
        ListNode *p=lists[0];
        for(int i=1;i<lists.size();i++)
            p=mergeTwoLists(p,lists[i]);
        return p;
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode dummy(-1);
        ListNode *p=&dummy;
        for(;l1!=NULL&&l2!=NULL;p=p->next){
            if(l1->val>l2->val){
                p->next=l2;
                l2=l2->next;
            }
            else{
                p->next=l1;
                l1=l1->next;
            }
        }
        p->next=l1!=NULL?l1:l2;
        return dummy.next;
    }
};

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

#include <algorithm>
#include <cstddef>
#include <vector>

typedef struct __node{
    ListNode* p;
    int val;
}Node;

bool cmp(Node& a, Node& b){
    return a.val <= b.val;
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        if(lists.empty())return nullptr;    // 如果lists为空直接退出
        vector<Node> arr;                   // 准备一个结构数组
        ListNode* head = new ListNode(-1);  // 准备一个头结点备用
        // 将全部节点的值和其指针存入数组
        for(vector<ListNode*>::iterator i = lists.begin(); i != lists.end(); i++){
            for(ListNode* j = *i; j != nullptr; j = j->next){
                Node t;
                t.p = j;
                t.val = j->val;
                arr.push_back(t);
            }
        }
        // 如果数组为空则退出
        if(arr.empty())return nullptr;
        // 对数组进行排序, 由于c++提供的排序是O(n * log n)的, 所以直接用
        sort(arr.begin(), arr.end(), cmp);
        // 接下来将排好序的结构元素数组恢复为链表
        ListNode* t = head;
        head->next = arr[0].p;
        for(int i = 0; i < arr.size(); i++){
            head->next = arr[i].p;
            head = head->next;
        }
        head->next = nullptr;
        return t->next;
    }
    
};

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* merge(struct ListNode* p1, struct ListNode* p2)
{
    //合并函数，合并两链表
    struct ListNode* mhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    mhead->next = p1;
    struct ListNode* cur = mhead;
    
    while(p1 && p2)
    {
        if(p1->val <= p2->val)
        {
            cur->next = p1;
            p1 = p1->next;
        }
        else
        {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    if(p1)
    {
        cur->next = p1;
    }
    if(p2)
    {
        cur->next = p2;
    }
    return mhead->next;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* mhead = NULL;
    while(listsLen--)
    {
        mhead = merge(mhead, lists[listsLen]);
    }
    return mhead;
}

//cpp

	
	

		
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        int b = 0;
        int num = lists.size();
        int* a = new int[2005];
        for(int i = 0;i<2005;i++){
            a[i] = 0;
        }
        ListNode* temp = nullptr;
        for(int i = 0;i<num;i++){
            temp = lists[i];
            while(temp){
                b = temp->val;
                a[b+1000]++;
                temp = temp->next;
            }
        }
        
        ListNode* p = nullptr;
        ListNode* head = nullptr;
        
        bool flag = false;
        for(int i = 0;i<=2000;i++){
            if(a[i]==0){
                continue;
            }else{

                while(a[i]>0){
                    temp = new ListNode(i-1000);
                    if(flag == false){
                        head = temp;
                        flag = true;
                        p = temp;
                        a[i]--;
                    }else{
                        p->next = temp;
                        p = temp;
                        a[i]--;
                    }
                }

            }
        }
        
        return head;
    }
};
	

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists.size()==0||lists == null) return null;
        ListNode head = lists.get(0);
        for(int i = 1;i<lists.size();i++) {
            head = getNode(head,lists.get(i));
        }
        return head;
    }
    public ListNode getNode(ListNode pHead1,ListNode pHead2) {
        if(pHead1==null) return pHead2;
        if(pHead2==null) return pHead1;
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        while(pHead1!=null&&pHead2!=null) {
            if(pHead1.val > pHead2.val) {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }else{
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }
            cur = cur.next;
        }
        if(pHead1==null) cur.next = pHead2;
        else cur.next = pHead1;
        return sentinel.next;
    }
}