剑指offer（十六）合并两个排序的链表

点击进入 牛客网题库：合并两个排序的链表

题目描述

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

这个题目，咋眼一看，我就想到直接比对后然后两个都接上，这样思路直接就乱了，然后一直没有做出来，弄了一上午，下午上来看了一个js大佬写的，然后看了之后了解了

就是定义一个哑节点，然后循环判断list1、list2中的大小，然后进行赋值在哑节点上就可以了

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) { 
          if(list1 == null) {
              return list2;
          }

          if(list2 == null) {
              return list1;
          }
          //哑节点
          ListNode node = new ListNode(0);
          ListNode tmpNode = node; 

          while(list1!=null && list2!=null) {
              if(list1.val <= list2.val) {
                 tmpNode.next = list1;
                 list1 = list1.next;
              }  else {
                  tmpNode.next = list2;
                  list2 = list2.next;
              }
              tmpNode = tmpNode.next;
          }

          if(list1!=null) {
             tmpNode.next = list1;
          } else if(list2!=null) {
            tmpNode.next = list2;
          }
          return node.next;
    }      
}