专栏首页架构说漫谈递归-链表合并

漫谈递归-链表合并

1. 第一个题目 合并两个有序链表

认真阅读题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4

线索

递归实现

新链表 是有将两个有序链表合并成的 假设有方法mergeTwoLists能实现这样功能。 通过大小判断之后 继续这个方法

实现

GO

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  if l1 == nil {    
    return l2  
  }  
  if l2 == nil {    
    return l1  
  }   
  if l1.Val < l2.Val {    
    l1.Next = mergeTwoLists(l1.Next, l2)      
    return l1  
  } 
  else {    
    l2.Next = mergeTwoLists(l1, l2.Next)      
    return l2  
  } 
}

c++

class Solution {
  public:  
  //Time complexity: O(n)  
  //Space complexity: O(0)  
  //Recursion  
  //输入:1->2->4, 1->3->4  
  //输出:1->1->2->3->4->4  
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)  {    
    if(l1 ==NULL)      
    {         
      return l2;      
    }      
    if(l2 ==NULL)      
    {        
      return l1;      
    }      
    if(l1->val<l2->val)      
    {       
      l1->next=mergeTwoLists(l1->next,l2);         
      return l1;      
    }
    else      
    {       
      l2->next=mergeTwoLists(l1,l2->next);        
      return l2;      
    }  
  } 
};

2. 难度升级 第二个问题 合并K个排序链表

认真阅读题目

  1. 合并K个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

关键:把每个链表看成一个元素,vector<元素>

分析

问题1. 这是k个 不是2个 感觉无从下手,转成成22合并 问题2. k个链表如何,通过什么方式知道 已经完成排序了呢。

步骤 1.如果是一个链表(从最简单开始) 就不需要合并 这就是结果

  1. 如果是多个 采用归并排序。对象就是n个链表。

代码

  • c
//Time complexity: O(logn)
    //Space complexity: O(0)
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
       int n=lists.size();
        if (n ==0)
        {
            return NULL;
        }
       return mergeLists(lists,0,n-1);
    }
     //
     ListNode* mergeLists(vector<ListNode*>& lists,int begin,int end)
     {
        //递归推出条件,只有一个元素
        if(begin == end)
        {
           return lists[begin];
        }

        int mid=(begin+end)/2;

        ListNode* first=mergeLists(lists,begin,mid);
        ListNode* second=mergeLists(lists,mid+1,end);

        return mergeTwoLists(first,second);

     }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        if(l1 ==NULL)
        {
             return l2;
        }
        if(l2 ==NULL)
        {
            return l1;
        }
        if(l1->val<l2->val)
        {
           l1->next=mergeTwoLists(l1->next,l2);
           return l1;
        }else
        {
           l2->next=mergeTwoLists(l1,l2->next);
           return l2;
        }
    }
  • go
func merge_K_Lists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    return sortmerge(lists, 0, len(lists)-1)
}
func sortmerge(lists []*ListNode, begin int, end int) *ListNode {
    if begin >= end {
        return lists[begin]
    }
    mid := (begin + end) / 2
    p1 := sort_merge(lists, begin, mid)
    p2 := sort_merge(lists, mid+1, end)
    return mergeTwoLists(p1, p2)

}

第三个题目 148. 排序链表 难度有升级了

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4

分析

链表无法通过下标直接定位 听过其他方法都不很合适 采用归并排序,数组通过下标来分段处理的,

链表如何分段? 指针特点出来了

代码

func sortList(head *ListNode) *ListNode {
    //只有一个元素 归并排序推出条件
    if head == nil || head.Next ==nil{
        return head
    }

    fast := head
    low := head
    for fast!=nil &&fast.Next!=nil&&fast.Next.!=nil{
        low=low.Next
        fast=fast.Next.Next

    }

    //一个链表分割成2个链表
    mid:=low.Next
    low.Next=nil //非常重要

    first := sortList(head) 
    second := sortList(mid)

    return mergeTwoLists(first,second)

}

第四个题目 remove-duplicates-from-sorted-list-ii

  1. 删除排序链表中的重复元素 II 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->1->1->2->3 输出: 2->3 题目理解

相同元素必须全部删除,如果比较相同元素, 需要2个变量,cur ,next [1,1,1,1] 最后一个元素1和谁比较呢

code

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head ==NULL || head->next ==NULL)
         {
            return head;
         }
         int pre=head->val;
         ListNode* temp;

         if(head->val ==head->next->val)
         {
             while(head && pre ==head->val)
             {
                temp=head;
                head=head->next;
                temp->next=NULL;
                delete temp;
             }
            return deleteDuplicates(head);

         }else
         {
             head->next=deleteDuplicates(head->next);
             return head;
         }
    }
};

remove-duplicates-from-sorted-list

83. 删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3

分析

链表问题没有简单问题 method 1

循环遍历 比较当前元素和下个元素 如果相同 删除当前元素(删除下一个元素会有问题的) 继续遍历 最坏情况 全部相同 [1,1,1,1,1,1,1]

code

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head ==NULL ||head->next ==NULL)
   {
      return head; //只有一个元素
   }

   //compare
   if(head->val ==head->next->val)
   {
     struct ListNode* temp=head;
     head=head->next;
     temp->next=NULL;
     free(temp);
     return deleteDuplicates(head);
     //如果相同,下一个节点可能相同,也可能不相同,需要递归才能知道。


   }else
   {
     head->next=deleteDuplicates(head->next);
     return head; //如果不相同,当前节点就是整个链表节点,继续递归
   }
}

总结

  1. 递归结束条件是什么 一个数组,一个链表 ,一个tree
  2. 变化一步过程是什么

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日一题-反转链表

    输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

    程序员小王
  • 二叉树的递归遍历

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节...

    程序员小王
  • 漫谈递归-回文链表

    执行用时: 20 ms, 在Palindrome Linked List的C++提交中击败了42.09% 的用户

    程序员小王
  • 链表插入排序

    一份执着✘
  • 超详细!图解「合并 K 个排序链表」

    今天分享的题目来源于 LeetCode 第 23 号问题:合并 K 个排序链表。本文采取两种思路进行分析。

    五分钟学算法
  • C#版 - 剑指offer 面试题9:斐波那契数列及其变形(跳台阶、矩形覆盖) 题解

    提交网址: http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&...

    Enjoy233
  • 图表系列——减小波动幅度

    逍遥之
  • 【未来驾驶新思路】王飞跃平行智能理论启发ACP自动驾驶,技术全解析

    编辑:张乾 【新智元导读】2月2日,在青岛2018国家智能产业峰会上,中国自动化学会副理事长兼秘书长王飞跃教授介绍了《第三轴心时代的智能产业》报告。王教授的平行...

    新智元
  • 使用openssl创建https证书

    从今天开始笔者打算和大家聊一聊http2这个协议,想要说清楚http2协议就必须亲手搭建一个http2的服务,并且对比http2和http1.1的特点,从而了解...

    挥刀北上
  • 8大数据看2016车市风水流转

    ? 2016年中国汽车产销均超2800万辆,连续8年蝉联全球第一。而在另一半球的美国,2016全年销量约为1754万辆,保持了7年的连续增长。中美两国车市就像...

    灯塔大数据

扫码关注云+社区

领取腾讯云代金券