线性表之单链表应用(3)

问题详细描述：

  将递增有序A、B两链表归并成一个按元素值非递增（允许有相同值）有序的链表C。

解题思路：

  利用A、B两表递增有序的特点，依次取出当前结点进行比较，将当前值较小者摘下，插入到C表的头部，由于采用的是头插法，最先找到的最小值结点将会在C表的尾部，依次类推，所以得到的C表则为非递增有序的。这里的递增递减性质需要根据代码具体修改实现。已在代码中给出提示。

/** * @TODO 两个数据元素类型为“整型”的递增（或者递减）单链表合并，由a单链表调用 * @param bFoll 单链表b * @return c 单链表c * （合并结果为非递减（或者非递增），取决于a,b链表的递增递减性质和合并函数的插入方法的选取） */ public FOLinkedList<Integer> merge(FOLinkedList<Integer> bFoll){ FOLinkedList<Integer> c = new FOLinkedList<Integer>(); FOLinkedNode<Integer> a = (FOLinkedNode<Integer>) this.header; FOLinkedNode<Integer> b = bFoll.header; Integer eTemp = new Integer(0); while(a != null && b != null){ if(a.getE()<=b.getE()){ eTemp = a.getE(); a = a.next; }else{ eTemp = b.getE(); b = b.next; } //这里可以采用头插法，或者尾插法 c.add(eTemp); // c.addFirst(eTemp); } if(a == null){ a = b; } while(a != null){ c.add(a.getE()); a = a.next; } return c; }

  将递增有序的A,B链表合并成非递减的链表C，采用尾插法即可实现。
  具体操作需要根据代码来进行修改，上述代码中可以修改插入元素的方法为头插法或者尾插法。