题解 | #合并有序链表#

//JAVA 好理解！

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */


public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        if(l1 ==null) return l2;
        if(l2 ==null) return l1;
        //设置一个新的链表的头结点。因为不知道l1和l2哪个头结点在前面。
        ListNode head = new ListNode(0); //临时的头节点
        ListNode Pnode = head;           //头结点的指针
        //开始拼接 l1 l2
        while(l1 !=null && l2 != null){
            if(l1.val >= l2.val){
                Pnode.next = l2;
                l2 = l2.next;  //开始比较l2的下个节点
            }else{
                Pnode.next = l1;
                l1 = l1.next;  //开始比较l1的下个节点
            }
            Pnode = Pnode.next; //拼接一个节点后，指针后移一步
        }
        //最后看l1 l2哪个还剩下节点，就直接拼在后面，
        if(l1!=null) Pnode.next=l1;
        if(l2!=null) Pnode.next=l2;
        //返回新链表的头结点。 head不是新链表的头结点，
        //head的下一个才是l1或者l2的第一个节点，才是头结点。
        return head.next;
    }
}