首页 计算机学科 java 编程题

# 合并两个有序链表

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

示例 1：

img

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

# 方法 1

  • 谁小，把谁链给 p，p 和小的都向后平移一位
  • 当 p1，p2 有一个为 Null，退出循环，把不为 null 的链给 p
    p1
1 3 8 9 null

	p2
2 4 null

  p
s 1

代码：

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while(p1 != null && p2 != null)
        {
          if(p1.val < p2.val)
          {
            p.next = p1;
            p1 = p1.next;
          }else
          {
            p.next = p2;
            p2 = p2.next;
          }
          p = p.next;
        }
        if(p1 != null)
        {
          p.next = p1;
        }
        if(p2 != null)
        {
          p.next = p2;
        }
        return s.next;
    }

# 方法 2

递归函数应该返回

  • 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
  • 返回之前，更新此节点的 next
mergeTwoLists(p1 = [1, 3, 8, 9], p2 = [2, 4])
{
   1.next = mergeTwoLists(p1 = [3, 8, 9], p2 = [2, 4])
	{
   	2.next = mergeTwoLists(p1 = [3, 8, 9], p2 = [4])
		{
   		3.next = mergeTwoLists(p1 = [8, 9], p2 = [4])
			{
 				4.next = mergeTwoLists(p1 = [8, 9], p2 = null)
				{
   				return [8, 9];
			   }
            return 4;
			}
         return 3;
		}
      return 2;
	}
   return 1;
}

代码：

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        if(p1 == null)
        {
          return p2;
        }
        if(p2 == null)
        {
          return p1;
        }
        if(p1.val < p2.val)
        {
          p1.next = mergeTwoLists(p1.next, p2);
          return p1;
        }else
        {
          p2.next = mergeTwoLists(p1, p2.next);
          return p2;
        }
    }