剑指offer 16.合并两个排序的链表

16.合并两个排序的链表

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

这题以前也做过的，只需要新建一个表头，然后比较两边的大小，依次加入新的链表，最后再把没用上的加到结尾即可。
now代表当前节点，base代表头结点。

代码

public class ListNode {

  int val;
  ListNode next = null;

  ListNode(int val) {
    this.val = val;
  }
}

public ListNode Merge(ListNode list1, ListNode list2) {
  if (list1 == null) {
    return list2;
  }
  if (list2 == null) {
    return list1;
  }
  ListNode base = null;
  ListNode now = null;
  while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
      if (base == null) {
        base = list1;
        now = list1;
      } else {
        now.next = list1;
        now = now.next;
      }
      list1 = list1.next;
    } else {
      if (base == null) {
        base = list2;
        now = list2;
      } else {
        now.next = list2;
        now = now.next;
      }
      list2 = list2.next;
    }
  }
  if (list1 == null) {
    now.next = list2;
  } else {
    now.next = list1;
  }
  return base;
}