题目描述

将两个升序列表合成一个升序列表并返回
示例
a:1—>2—>5
b:1—>3—>5
返回 1—>1—>2—>3—>5

思路

用a链表的第一个元素 和b链表的第一个元素值比较
如果a 的第一个元素值小于b链表第一个元素的值 则 a指向 a.next= （a.next 和 b 合成后的链表）
最后return a
反之 a的第一个元素的值大于 b链表的第一个元素的值 则 b指向 b.next=(b.next 和 a 合成后的链表)
递归退出条件 当 a==null 或者 b==null

代码示例 

  1. public class ListNode
  2. {
  3.             public int val;
  4.             public ListNode next;
  5.             public ListNode(int x) { val = x; }
  6. }
  1. public static ListNode MergeTwoLists(ListNode l1,ListNode l2)
  2. {
  3.     if (l1==null)
  4.     {
  5.         return l2;
  6.     }
  7.     if (l2 == null)
  8.         return l1;
  9.     if (l1.val < l2.val)
  10.     {
  11.         l1.next = MergeTwoLists(l1.next, l2);
  12.         return l1;
  13.     }
  14.     else
  15.     {
  16.         l2.next = MergeTwoLists(l2.next,l1);
  17.         return l2;
  18.     }
  19. }
  1.  //构造一个链表
  2.  public static ListNode getListNode(List<int> lis)
  3.  {
  4.      if (lis.Count <= 0)
  5.          return null;
  6.      ListNode head = new ListNode(lis[0]);
  7.      lis.RemoveAt(0);
  8.      head.next = getListNode(lis);
  9.      return head;
  11.  //打印列表
  12.  public static void PrintListNode(ListNode ls)
  13.  {
  14.      if (ls == null)
  15.          return;
  16.      Console.WriteLine(ls.val);
  17.      PrintListNode(ls.next);
  18.  }

  1. 最后的调用
  2.  static void Main(string[] args)
  3.  {
  4.      ListNode l1= getListNode(new List<int> {1,3,5 });
  5.      ListNode l2 = getListNode(new List<int> { 1, 2, 5 });
  6.      ListNode res= MergeTwoLists(l1,l2);
  7.      PrintListNode(res);
  8.      Console.ReadKey();
  9.  }