Android面试---组装两个有序链表并合并

一、将数组中有序数据加到链表（支持重复）

    int[] arrs = {1, 3, 4, 5, 6, 7, 8, 8, 9};
    int[] arrs2 = {2, 5, 7, 10, 11};
    ListNode listNode = new ListNode(arrs);
    ListNode listNode2 = new ListNode(arrs2);

  //node
   class ListNode {
   public ListNode( ListNode next,int val) {
    this.val = val;
    this.next = next;
   }

   int val;
   ListNode next;
  public ListNode(int val) {
    this.val = val;
  }
  //add []
  public ListNode(int[] arrs) {
    if (null == arrs || arrs.length == 0) throw new IllegalArgumentException("no null");
    this.val = arrs[0];
    ListNode curr=this;
    for (int i = 1; i < arrs.length; i++) {
        int data = arrs[i];
        curr.next=new ListNode(data);
        curr=curr.next;
    }
  }
}

二、有序链表并合并

    /**
     * 合并得到一个有序的链表
     * int[] arrs = {1, 3, 4, 5, 6, 7, 8, 8, 9};
     * int[] arrs2 = {2, 5, 7, 10, 11};
     */
    private static ListNode addMergeElement(ListNode l1, ListNode l2) {
    if (null == l1) return l2;
    if (null == l2) return l1;
    //1、add head
    ListNode orgHead = new ListNode(l1, -1);
    ListNode insertHead = new ListNode(l2, -1);
    ListNode currOrgNode = orgHead.next;
    ListNode currInsert = insertHead.next;
    while (null != currInsert) {
        //4连接较大的数据的值
        if (currOrgNode.next == null) {
            currOrgNode.next = currInsert;
            break;
        }
        if ((currOrgNode.val <= currInsert.val) && (currInsert.val < currOrgNode.next.val)) {
            //2拿出要加入的数据
            ListNode add = new ListNode(currInsert.val);
            add.next = currOrgNode.next;
            currOrgNode.next = add;
            //3下个个节点
            currInsert = currInsert.next;
        } else {
            currOrgNode = currOrgNode.next;
        }
    }
    return orgHead.next;
}

效果