[Java] java编程题之合并两个排序的链表

/**
 * 
 * 剑指offer编程题（java实现)——第16题：合并两个排序的链表
 * 
 * 输入两个单调递增的链表，输出两个链表合成后的链表， 当然我们需要合成后的链表满足单调不减规则。
 * 
 */
public class test16 {
 public static listnode merge(listnode list1, listnode list2) {
 if (list1 == null) { // 首先判断是否有链表为空
 return list2;
 } else if (list2 == null) {
 return list1;
 }
 listnode end1 = list1;
 listnode end2 = list2;
 listnode tmp; //end1和end2分别代表两个链表，tmp用于中间合成链表
 
 if (end1.val > end2.val) {//把首节点小的链表看作end1
 tmp = end1;
 end1 = end2;
 end2 = tmp;
 } else {
 
 }
 listnode newnode = end1;//用于最终返回的链表首节点
 
 while (end1.next != null && end2.next != null) { //将链表2中的元素插入链表1中合适的位置
 if (end1.val <= end2.val && end1.next.val >= end2.val) {
 tmp = end2.next;
 end2.next = end1.next;
 end1.next = end2;
 end1 = end2;
 end2 = tmp;
 } else {
 end1 = end1.next;
 }
 }
 
 if (end1.next == null) {//如果链表1到尾节点了则直接连接剩下的链表2中的首节点
 end1.next = end2;
 return newnode;
 } else {
 if (end1.next != null && end2.next == null) {//如果链表2到尾节点了则将链表2中所剩下的最后一个节点插入链表1
 while (end2 != null) {
  if (end1.val <= end2.val && end1.next.val >= end2.val) {
  end2.next = end1.next;
  end1.next = end2;
  break;
  } else {
  end1 = end1.next;
  if (end1.next == null) {//链表2最后的节点最大
  end1.next = end2;
  break;
  }
  }
 }
 }
 return newnode;
 }
 }
 
 public static void main(string[] args) {
 listnode list1 = new listnode(1);
 list1.next = new listnode(3);
 list1.next.next = new listnode(5);
 listnode list2 = new listnode(2);
 list2.next = new listnode(4);
 list2.next.next = new listnode(6);
 system.out.println(merge(list2, list1));
 }
 
 // 链表
 public static class listnode {
 int val;
 listnode next = null;
 
 listnode(int val) {
 this.val = val;
 }
 }
}