21. 合并两个有序链表

题意：

解题思路：

时间复杂度：O(n)
思路：
    1. 新建头部虚拟节点dummy，设置cur指向dummy；
    2. 循环比较l1,l2大小，如果l1 <= l2，则cur指向l1,同时l1后移，反之指向l2；
    3. 一轮过后，cur后移一位；
    3. 当条件不满足时，将剩余不为空的节点，接在cur后面；
    4. 最后返回虚拟节点的下一个节点即可；

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    function mergeTwoLists($l1, $l2) {
        $dummy = new ListNode(0);
        $curNode = $dummy;
        while ($l1 != null && $l2 != null) {
            if ($l1->val <= $l2->val) {
                $curNode->next = $l1;
                $l1 = $l1->next;
            } else {
                $curNode->next = $l2;
                $l2 = $l2->next;
            }
            $curNode = $curNode->next;
        }
        $curNode->next = $l1 == null ? $l2 : $l1;
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1 
            l1 = l1.Next
        } else {
            cur.Next = l2 
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }
    return dummy.Next
}