LeetCode#21-Merge Two Sorted Lists-合并两个有序链表

一、题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4  输出:1->1->2->3->4->4  

二、题解

  • 解法1:递归

终止条件:两条链表分别为 l1 和 l2,当 l1 为空或 l2 为空时结束。
如何递归:判断 l1 和 l2 头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果。(调用递归)

时间复杂度:O(n+m);空间复杂度:O(n+m)。

<?php    class ListNode {      public $val = 0;      public $next = null;      function __construct($val) {          $this->val = $val;      }  }    /**   * @param ListNode $l1   * @param ListNode $l2   * @return ListNode   */  function mergeTwoLists($l1, $l2) {      if ($l1 == null) {          return $l2;      }      if ($l2 == null) {          return $l1;      }        if ($l1->val <= $l2->val) {          $l1->next = mergeTwoLists($l1->next, $l2);          return $l1;      }      if ($l2->val <= $l1->val) {          $l2->next = mergeTwoLists($l2->next, $l1);          return $l2;      }  }    /**   * 构建一个单链表(将数组转换成链表)   */  function createLinkedList($arr)  {      $linkedList = [];      $current = new ListNode(array_shift($arr)); //头节点      while (!empty($arr)) {          while ($current->next != null) {              $linkedList[] = $current;              $current = $current->next;          }          $current->next = new ListNode(array_shift($arr));      }        return $linkedList[0];  }    $l1 = createLinkedList([1,2,4]);  $l2 = createLinkedList([1,3,5]);    $res = mergeTwoLists($l1, $l2);  print_r($res);  

得到的结果如下:

ListNode Object  (      [val] => 1      [next] => ListNode Object          (              [val] => 1              [next] => ListNode Object                  (                      [val] => 2                      [next] => ListNode Object                          (                              [val] => 3                              [next] => ListNode Object                                  (                                      [val] => 4                                      [next] => ListNode Object                                          (                                              [val] => 5                                              [next] =>                                          )                                  )                          )                  )          )  )  
  • 解法2:迭代

设定一个哨兵节点,用来返回合并后的链表,维护一个 pre 节点,调整它的 next 指针。

当 l1 当前位置的值小于等于 l2,就将 pre 节点的 next 指向 l1 的这个值,同时将 l1 指针往后移一个。反之则对 l2 做同样的操作,直到 l1 或者 l2 指向 null。当循环终止的时候,l1 和 l2 至多有一个是非空的。

由于输入的两个链表都是有序的,所以不管哪个链表是非空的,只需要将剩下的那个非空链表接在合并链表的后面,并返回合并链表即可。

时间复杂度:O(n+m);空间复杂度:O(n+m)。

/**   * @param ListNode $l1   * @param ListNode $l2   * @return ListNode   */  function mergeTwoLists($l1, $l2) {      // 设置一个哨兵      $node = new ListNode(null);      $pre = $node;      while ($l1 != null && $l2 != null) {          if ($l1->val < $l2->val) {              $pre->next = $l1;              $l1 = $l1->next;          } else {              $pre->next = $l2;              $l2 = $l2->next;          }          $pre = $pre->next;      }      if ($l1 == null) {          $pre->next = $l2;      }      if ($l2 == null) {          $pre->next = $l1;      }        return $node->next;  }