剑指OfferJZ16：合并两个排序的链表-java版

JZ16 合并两个排序的链表

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

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

建立一个用于存放合并后的链表的大链表 listNode 由于两个链表中数字都是有序的，我们可以这样：

• 如果两个链表list1和list2都有数字，这时我们将链表list1的第一个数和链表list2的第一个数比较，将小的那个数移入到listNode中，以此类推，

• 当合并后只剩有一个链表有数字时，直接将这个链表剩下的所有数字移入listNode中

该思路类似于归并排序中的“合”，只是归并排序中用的是数组，而这道题用的是链表罢了，参考归并排序 解题思路比较简单，但这道链表算法题需要注意一个问题： 一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。

哨兵，顾名思义，是用来解决国家之间边界问题的，不直接参与生产活动。同样，计算机科学中提到的哨兵，也用来解决边界问题。 不带哨兵节点的链表，插入或删除操作发生在第一个节点时，表头指针都要变化，需要额外的处理。带哨兵节点的链表，插入或删除时，不论操作的位置，表头都不变，不需要额外的判断； 所以我们可以申请一个头结点，作为原本的第一个结点的前驱结点，问题也就解决了。（如果用的是双链表，就需要在头尾各加一个哨兵）

使用哨兵的其它好处： 在循环语句中使用哨兵的好处往往在于可以使代码简洁，而非提高速度。举例来说，使用哨兵使链表的代码变得简洁了 我们应当慎用哨兵。假如有许多个很短的链表，它们的哨兵所占用的额外的存储空间会造成严重的额存储浪费。

public class jz16 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode listNode = new ListNode(0);//合并的链表
        ListNode cur = listNode;//cur哨兵节点：解决边界问题，使代码更简洁
        while(list1!=null && list2!=null){
            if(list1.val