[NC]33. 合并两个排序的链表【链表二路归并】

🚩传送门：牛客题目

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

示例 1:

输入：{1,3,5},{2,4,6} 返回值：{1,2,3,4,5,6}

解题思路：二路归并

双指针二路归并，由于合并过程中头结点和其他结点操作不一样，因此为了统一操作先给新头指针一个头节点

我的代码

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
       ListNode list1Head=list1;
       ListNode list2Head=list2;
       //1.为了简便操作,new 出一个头节点 
       ListNode NewHead=new ListNode(-1);
       ListNode NewTail=NewHead;
       //2.双指针非空,比较插入
       while(list1Head!=null&&list2Head!=null){
           if(list1Head.val<list2Head.val){
               NewTail.next=list1Head;
               list1Head=list1Head.next;
           }
           else{
               NewTail.next=list2Head;
               list2Head=list2Head.next;
           }
           NewTail=NewTail.next;
       }
       //3.2链表空了,直接将剩余1链表插入即可
       if(list1Head!=null){
           NewTail.next=list1Head;
       }
       //4.1链表空了,直接将剩余2链表插入即可
       if(list2Head!=null){
           NewTail.next=list2Head;
       }
       //5.抛弃多余的头节点
       NewHead=NewHead.next;
       return NewHead;
    }
}