美文网首页
25.合并两个有序链表

25.合并两个有序链表

作者: HamletSunS | 来源:发表于2019-07-31 15:33 被阅读0次

    思路:
    基础题目,设置3个指针,2个分别指向2个有序链表,第3个用来拼接最后的合并链表(保存好要返回的头结点)。没什么好说的。
    应用:
    链表排序。对链表进行归并排序的时候,本题的算法相当于是归并排序中的merge操作。

    拓展:链表排序
    难点:

    1. 找链表中点
    2. merge操作的实现

    逐个攻破:

    • 先来说merge操作的实现
      有2种方式,1种是递归,1一种是循环。其中递归方便理解,但空间复杂度为O(n)(系统栈的调用)
      递归实现:
    TreeNode* merge(TreeNode *a,TreeNode *b){
    //定义终止条件  
    if(a==nullptr)
          return b;
    if(b==nullptr)
          return a;
    //开始递归过程
    if(a->val<=b->val){
    a->next=merge(a->next,b);
    reutrn a;
    }  
    else{
    b->next=merge(a,b->next);
    return b;
    }
    }
    

    循环实现merge

    TreeNode *merge(TreeNode *a,TreeNode *b){
    //judge illegal
    if(a==nullptr)
    return b;
    if(b==nullptr)
    return a;
    TreeNode *c,*head;
    if(a->val<=b->val){
     c=a;
    a=a->next;
    }
    else{
    c=b;
    b=b->next;
    }
    head=c;
    while(a&&b){
    if(a->val<=b->val){
    c->next=a;
    a=a->next;
    }
    else{
    c->next=b;
    b=b->next;
    }
    c=c->next;
    }
    c->next=nullptr;
    if(a!=nullptr)
    c->next=a;
    if(b!=nullptr)
    c->next=b;
    return head;
    }
    

    可见循环的代码比递归的代码要冗余许多,但是执行效率会更高,两种实现方式都不是很难,其实就是简单的逻辑判断,判断一下是a链表的值还是b链表的值大,分别处理即可

    • 找到链表中点
      采用快慢指针的方法,快指针走2步,慢指针走一步,因为要切分链表一定要明确切分的范围,否则容易犯迷糊,比如把链表切分成[head,slow],[slow->next,null]两部分或者[head,slow->prior],[slow,null]两部分,定义好切分的范围后,写代码会思路更加清晰,不容易出错。
      另外值得注意的是链表不具备随机访问的能力,因此我们需要额外设置一个指针split来标记我们的链表切分点(可以标记slow节点的前一个或者后一个节点)

    逻辑代码(不推荐封装成函数,因为我们需要split和slow两个节点,封装成函数如果用cpp的话还是挺麻烦的)
    find the middle point in a linkedList

    vector<TreeNode *>findMP(TreeNode *head){
    //judge illeagal
    if(head==nullptr)
    return nullptr;
    TreeNode *slow=head,*fast=head,*split=head;
    while(fast&&fast->next){
    fast=fast->next->next;
    split=slow;//mark the slow->prior
    slow=slow->next;
    }
    return {split,slow} //[head,split],[slow,nullptr]
    }
    
    整体实现:  
    目前我们已经实现了找到链表中点和merge操作,那么我们就可以用归并排序进行链表排序了。  
    ```cpp
    TreeNode *sortList(TreeNode *head){
     //judge illeagal
    if(head==nullptr||head->next==nullptr)
    return head;
    //find the middle point  
    
    vector<TreeNode> split=findMP(head);
    split[0]->next=nullptr;
    head=sortList(head);
    split[1]=sortList(split[1]);
    merge(split[1]);
    
    }
    

    循环实现:(待补充)

    相关文章

      网友评论

          本文标题:25.合并两个有序链表

          本文链接:https://www.haomeiwen.com/subject/sbltdctx.html