图解有序链表合并

大数据记事本 2020-07-15

816

有序链表的合并也是常见的链表问题，这里通过两种方法来讲解：

归并法
递归法

定义结点类型：

class Node {
int no;
    Node next;
public Node(int no) {
this.no = no;
    }
@Override
public String toString() {
return "Node{" + "no=" + no + "}";          
    }
}

一、归并法

归并法和归并排序的merge过程类似，通过两个指针分别遍历两个链表，然后比较结点数据值的大小，将数据值较小（升序排列）的结点依次添加到新的链表中，指针后移，直到其中一个链表遍历完毕，最后将另一个链表的剩余结点直接添加到新的链表末尾，完成合并。具体过程如下图：

代码实现：

public static Node mergeSortedLinkedList(Node head1,Node head2){
    //如果有一个链表为空，直接返回另一个链表
    if(head1==null)return head2;
    if (head2==null)return head1;
    //新建一个头结点，并定义一个辅助指针tmp
    Node new_head = new Node(0);
    Node tmp=new_head;
    //两个指针分别指向链表的第一个结点
    Node p1=head1.next;
    Node p2=head2.next;
    //两个链表都没遍历完
    while(p1!=null&&p2!=null){
        if (p1.no<=p2.no){
            tmp.next=p1;
            p1=p1.next;
            tmp=tmp.next;
        }else{
            tmp.next=p2;
            p2=p2.next;
            tmp=tmp.next;
        }
    }
    //p1不为null说明第一个链表还有结点没遍历完，而第二个链表已遍历完
    //将剩余结点放在新链表的末尾
    if (p1!=null){
        tmp.next=p1;
    }
    if (p2!=null){
        tmp.next=p2;
    }
    return new_head;
}

二、递归法

递归法的思路是：选出两个链表中数据值最小的结点，然后将该链表剩余部分的结点作为一个链表，和另一个链表再次进行合并成一个新链表，该数据值最小的结点的next域指向后面合并成的新链表；然后递归，直到遍历完其中一个链表，将另一个链表剩余结点放到合并链表的末尾。如下图所示：

代码实现：

//对于带头结点的链表，可以增加一个参数，标记参数链表是否带头结点，
//如果带头结点，比较的应该是其next域对应结点的值；否则直接比较结点的值
public static Node mergeSortedLinkedList2(Node head1,Node head2,boolean isHead){
    //递归结束条件：其中一个链表为空
    if(head1==null)return head2;
    if (head2==null)return head1;


     if(isHead){//如果是头结点，应该比较其next域对应结点的值
         if (head1.next.no<=head2.next.no){
             head1.next.next=mergeSortedLinkedList2(head1.next.next,head2.next,false);
             return head1;
         }else{
             head2.next.next=mergeSortedLinkedList2(head1.next,head2.next.next,false);
             return head2;
         }
     }else{//如果不是头结点，直接比较结点的值
         if (head1.no<=head2.no){
             head1.next=mergeSortedLinkedList2(head1.next,head2,false);
             return head1;
         }else{
             head2.next=mergeSortedLinkedList2(head1,head2.next,false);
             return head2;
         }
     }
}

如果是不带头结点的链表，可以采用下面的代码：

public static Node mergeSortedLinkedList2(Node head1,Node head2){
    //递归结束条件：其中一个链表遍历完
    if(head1==null)return head2;
    if (head2==null)return head1;
    
    if(head1.no<=head2.no){
        head1.next=mergeSortedLinkedList2(head1.next,head2);
        return head1;
    }else{
        head2.next=mergeSortedLinkedList2(head1,head2.next);
        return head2;
    }
}

数据库

文章转载自大数据记事本，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

图解有序链表合并

评论