对python实现合并两个排序链表的方法详解

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1、迭代方法

  def Merge(self, pHead1, pHead2):
    p1, p2 = pHead1, pHead2
    if p1 and p2:
      if p1.val < p2.val:
        head = p1
        p1 = p1.next
      else:
        head = p2
        p2 = p2.next
      cur = head
    elif p1:
      return p1
    else:
      return p2

    while p1 and p2:
      if p1.val < p2.val:
        cur.next = p1
        p1 = p1.next
      else:
        cur.next = p2
        p2 = p2.next
      cur = cur.next
    if p1:
      cur.next = p1
    else:
      cur.next = p2
    return head

2、递归方法

  def Merge_rcv(self, pHead1, pHead2):
    if not pHead1:
      return pHead2
    if not pHead2:
      return pHead1
    if pHead1.val < pHead2.val:
      pres = pHead1
      pres.next = self.Merge(pHead1.next, pHead2)
    else:
      pres = pHead2
      pres.next = self.Merge(pHead1, pHead2.next)
    return pres

附注：

递归算法运行逻辑看着复杂,但是形式上都是简单的.每一层都表达了”当前结点要做的任务”.

思考递归算法的步骤应该是

1) 明确每一层要做的任务,eg,选择链表中较小值作为当前结点

2) 明确每一层的任务的完结点和递归连接点,eg,在pres.next处进行下一层递归

3) 明确return条件,eg,当p1,p2其中有一个为空时,递归任务结束

几乎所有的递归算法都可以沿着这三个要求思考构造,很自然不怕写递归算法,三个问题能自己在脑里回答出来,稍加修饰就是一个完整的递归算法.

这也是函数式编程的魅力所在.

以上这篇对python实现合并两个排序链表的方法详解就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python算法题 链表反转

    python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • Python实现合并两个有序链表的方法示例

    Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

  • Python3实现的判断回文链表算法示例

    本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置

  • 基于python实现从尾到头打印链表

    这篇文章主要介绍了基于python实现从尾到头打印链表,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList. 思路 遍历链表,把结构保存在list里面,然后把list逆序输出 代码 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None

  • c语言链表基本操作(带有创建链表 删除 打印 插入)

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LEN sizeof(struct Student)struct Student{    long num;    float score;    struct Student*next;};int n;int main(){    /*-----------------------------程序描述----------

  • C++实现打印两个有序链表公共部分的方法

    本文实例讲述了C++实现打印两个有序链表公共部分的方法.分享给大家供大家参考,具体如下: 题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分. 解题思路及代码: 1.head1的值小于head2,则head1往下移动 2.head1的值小于head2,则head2往下移动 3.相等则打印任何一个链表节点的值,head1和head2都往下移动. 4.当head1或head2移动到NULL,终止. 算法C++代码: typedef struct Node { int da

  • 面试题:用 Java 逆序打印链表

    昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 volatile 关键字,不少朋友问我,到底为啥要加 volatile 这个关键字呀,而它,到底又有什么神奇的作用呢? 对 volatile 这个关键字,在昨天的讲解中我们简单说了一下:被 volatile 修饰的共享变量,都会具有下面两个属性: 保证不同线程对该变量操作的内存可见性. 禁止指令重排序. 共享变量:如果一个变量在多个线程的工作内存中都存在副本,那么这个变量就是这几个线程的共享变量. 可见性:一个线

  • Java编程实现从尾到头打印链表代码实例

    问题描述:输入一个链表的头结点,从尾巴到头反过来打印出每个结点的值. 首先定义链表结点 public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } 思路1:此题明显想到是利用栈的思想,后进先出,先遍历链表,依次将结点值进栈.最后在遍历栈出栈. public static Stack<Integer> printListReverse_Stack(ListNode li

  • PHP从尾到头打印链表实例讲解

    题目 输入一个链表,从尾到头打印链表每个节点的值. 题解 一种是使用栈. 第二种是递归. 代码 //递归版本 function printListFromTailToHead($head) { if($head == NULL){ return []; } $arr = array(); $cur = $head; if($cur->next != null){ $arr = printListFromTailToHead($cur->next); } array_push($arr, $cu

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • TypeScript合并两个排序链表的方法详解

    TypeScript合并两个排序链表的方法详解

    目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • Python数据合并的concat函数与merge函数详解

    Python数据合并的concat函数与merge函数详解

    目录 一.concat函数 1)横向堆叠与外连接 2) 纵向堆叠与内链接 二.merge()函数 1)根据行索引合并数据 2)合并重叠数据 一.concat函数 1.concat()函数可以沿着一条轴将多个对象进行堆叠,其使用方式类似数据库中的数据表合并pandas.concat(objs, axis=0, join=’outer’, join_axes=None, ignore_index=False, keys=None, levels=None, verify_integrity=Fals

  • 在python中按照特定顺序访问字典的方法详解

    最近使用python写一些东西,在参考资料的时候发现字典是没有顺序的,那么怎么样按照一定顺序访问字典呐,我找到了一个小方法: 假设一个字典是: D = {'a': '1', 'b': '2', 'c': '3'} 如果我们要按照a, b, c的顺序访问字典,可以借助一个列表,比如说: L = list(D.keys()) L.sort() for key in L: print(key, 'is' D[key]) 输出为: a is 1 b is 2 c is 3 需要倒序的话只需使用倒序函数排

  • 对python tkinter窗口弹出置顶的方法详解

    如果想要python 的tkinter窗口置顶,加上下面两句即可实现root窗口的置顶显示,可以用于某些程序的消息提示,能够弹出到桌面显示 root = Tk() root.wm_attributes('-topmost',1) 以上这篇对python tkinter窗口弹出置顶的方法详解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • 基于Python的Post请求数据爬取的方法详解

    为什么做这个 和同学聊天,他想爬取一个网站的post请求 观察 该网站的post请求参数有两种类型:(1)参数体放在了query中,即url拼接参数(2)body中要加入一个空的json对象,关于为什么要加入空的json对象,猜测原因为反爬虫.既有query参数又有空对象体的body参数是一件脑洞很大的事情. 一开始先在apizza网站 上了做了相关实验才发现上面这个规律的,并发现该网站的请求参数要为raw形式,要是直接写代码找规律不是一件容易的事情. 源码 import requests im

  • 更改Python的pip install 默认安装依赖路径方法详解

    前言 声明:python版本3.6,以下讨论的Python也都是适用于3.x版本 在实际使用安装python的pip安装 依赖库是非常的便捷的. 而且一般大家使用的都是安装Anaconda 来学习和实践python项目. 我们通常都是直接就是使用 pip install **** 其中****代表就是安装的依赖库名或者包名. 但是简单的背后就是,我们的最重要的系统盘C盘都是逐渐满了.更关键是你满完之后还不好去删除或者将一些依赖库放在别的盘的路径下,这就是一件非常糟糕的事情了. 所以今天,为了拯救

  • 对python使用telnet实现弱密码登录的方法详解

    系统环境: 64位win7企业版 python2.7.10 2016.08.16修改内容: 1)read_until()函数是可以设置timeout的,之前不能获取到password之后的返回是因为调用read_some()函数次数不够,没有读取到返回信息 2)如果不设置read_until()函数的timeout值,那么程序将一直建立连接而不会关闭,导致程序永远没有返回,所以设置timeout还是有必要的 3)不同服务器返回的内容是不一样的,例如网络设备radware返回就不是"login:&

随机推荐