21. 合并两个有序链表

思路

三指针遍历,利用两个指针遍历分别遍历两个链表,并比较对应值的大小,新指针指向小的节点,小的一方的指针也要往后移。

最后,要处理一下[一个长链,一个短链,长链还没走完]的情况。

复杂度

时间复杂度:O(m)

空间复杂度:O(1)

代码

/**
 * 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 {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function mergeTwoLists($l1, $l2) {
        $list = new ListNode(-1);
        $p = $list;
        // 只有一个链遍历完,则退出
        while($l1 != null && $l2 != null){

            if($l1->val <= $l2->val){
                $p->next = $l1;
                $l1 = $l1->next;
            } else {
                $p->next = $l2;
                $l2 = $l2->next;
            }

            $p = $p->next;
        }

        // 若一个长链,一个短链,长链还没走完
        $p->next = $l1 === null ? $l2 : $l1;

        // 去除头节点
        return $list->next;
    }
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    list := &ListNode{
        Val:  0,
        Next: nil,
    }
    p := list

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            p.Next = list1
            list1 = list1.Next
        } else {
            p.Next = list2
            list2 = list2.Next
        }

        p = p.Next
    }

    if list1 == nil {
        p.Next = list2
    }

    if list2 == nil {
        p.Next = list1
    }

    return list.Next
}

results matching ""

    No results matching ""