Java数据结构-线性表之单链表应用-单链表合并

心已赠人 2022-08-02 12:40 301阅读 0赞

问题详细描述：

将递增有序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，采用尾插法即可实现。  
  具体操作需要根据代码来进行修改，上述代码中可以修改插入元素的方法为头插法或者尾插法。

**该算法的时间性能由两待合并链表的的元素个数来决定，即为O(m+n)**