Python实现单链表中元素的反转

给定一个单链表，将其反转。其实很容易想到，只需要修改每个结点的指针指向:即令后一个结点指向前一个结点，并且将表头指针指向最后一个结点即可。

这个过程可以用循环实现，也可以用递归来实现。

1、用循环来实现：

class LNode:
    def __init__(self, elem):
        self.elem = elem
        self.pnext = None
 
def reverse(head):
    if head is None or head.pnext is None: #如果输入的链表是空或者只有一个结点，直接返回当前结点
        return head
    pre = None #用来指向上一个结点
    cur = newhead = head #cur是当前的结点。newhead指向当前新的头结点
    while cur:
        newhead = cur
        temp = cur.pnext
        cur.pnext = pre #将当前的结点的指针指向前一个结点
        pre = cur
        cur = temp
    return newhead
 
if __name__=="__main__":
    head = LNode(1)
    p1 = LNode(2)
    p2 = LNode(3)
    head.pnext = p1
    p1.pnext = p2
    p = reverse(head)
    while p:
        print(p.elem)
        p = p.pnext

2、用递归来实现：

class LNode:
    def __init__(self, elem):
        self.elem = elem
        self.pnext = None
 
def reverse(head):
    if not head or not head.pnext:
        return head
    else:
        newhead = reverse(head.pnext)
        head.pnext.pnext = head #令下一个结点的指针指向当前结点
        head.pnext = None #断开当前结点与下一个结点之间的指针指向联系，令其指向空
        return newhead
 
 
if __name__=="__main__":
    head = LNode(1)
    p1 = LNode(2)
    p2 = LNode(3)
    head.pnext = p1
    p1.pnext = p2
    p = reverse(head)
    while p:
        print(p.elem)
        p = p.pnext

以下是图解递归的详细过程：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python版单链表反转

    python版单链表反转

    本文实例为大家分享了vue + element ui实现锚点定位的具体代码,供大家参考,具体内容如下 代码如下: class Node(object):     def __init__(self, elem, next_=None):         self.elem = elem         self.next = next_   def reverseList(head):     if head == None or head.next==None:  # 若链表为空或者仅一个数就

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

  • 单链表反转python实现代码示例

    单链表反转python实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • python反转单链表算法题

    python反转单链表算法题

    现在算法是大厂面试的必考题,而且越来越难,已经不是简单的列表,字符串操作了,会涉及到各种数据结结构.单链表的反转也是经常考的一道题,里面故在此记录一下. 1.链表的特点: 顺序存储元素,但是元素在空间上是不连续的,所以在链表每个元素中除了存储元素的值,还会存储下一个元素的地址,单链表的话就只有指向下一个元素的指针,双向链表的话还会有指向前一个元素的指针.正是由于链表以上的存储特点,在做插入和删除操作时只需要断开指针的连接,不需要移动后面的数据,所以对链表修改的效率会很高,但是查找的效率会很低,这

  • Python实现单链表中元素的反转

    Python实现单链表中元素的反转

    给定一个单链表,将其反转.其实很容易想到,只需要修改每个结点的指针指向:即令后一个结点指向前一个结点,并且将表头指针指向最后一个结点即可. 这个过程可以用循环实现,也可以用递归来实现. 1.用循环来实现: class LNode:     def __init__(self, elem):         self.elem = elem         self.pnext = None   def reverse(head):     if head is None or head.pnex

  • python实现单链表中删除倒数第K个节点的方法

    本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li

  • python/golang 删除链表中的元素

    先用使用常规方法,两个指针: golang实现: type Node struct { value int next *Node } type Link struct { head *Node tail *Node lenth int } // 向链表中添加元素 func (link *Link) add(v int) { if link.lenth == 0 { // 当前链表是空链表 link.head = &Node{v, nil} link.tail = link.head link.l

  • C++和python实现单链表及其原理

    C++和python实现单链表及其原理

    目录 一.链表的基本概念 二.单链表 1.python实现 (1)节点设计 (2)链表类:Single_Linked_List (3)判断链表是否为空:is_empty()函数 (4)头插法:add()函数 (5)尾插法:append()函数 (6)在任意位置插入:insert()函数 (7)计算链表长度:get_length()函数 (8)遍历所有节点:traversal()函数 (9)搜索:search()函数 (10)删除:delete()函数 2.C++实现 (1)节点设计 (2)链表类

  • Python针对给定列表中元素进行翻转操作的方法分析

    Python针对给定列表中元素进行翻转操作的方法分析

    本文实例讲述了Python针对给定列表中元素进行翻转操作的方法.分享给大家供大家参考,具体如下: 题目 给定一列表,翻转其中的元素,倒序输出 做法很简单,这里给出来两种做法,第一种最简单使用的是针对列表的切片操作,下面是具体实现 #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:翻转列表 ''' def inverse_list1(num_list): ''''' 翻转列表 ''' print num_list[::-1]

  • python环形单链表的约瑟夫问题详解

    题目: 一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点. 这个问题就是著名的约瑟夫问题. 代码: 首先给出环形单链表的数据结构: class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedL

  • python实现求解列表中元素的排列和组合问题

    求解列表中元素的排列和组合问题这个问题之前就遇到过几次没有太留意,最近在做题的时候遇上挺多的排列组合问题的,想来有必要温习一下了,今天花点时间写一下,之前都是手工写的,后来知道可以直接使用python的内置模块就可以完成这个工作了,今天就使用python的itertools模块来完成这个工作,一共解决四个问题: 1.生成排列,列表中元素不允许重复出现 2.生成排列,列表中元素可以重复出现 3.生成组合,不限元素个数,列表中元素不允许重复出现 4.生成组合,不限元素个数,列表中元素可以重复出现 因

  • Java链表中元素删除的实现方法详解【只删除一个元素情况】

    本文实例讲述了Java链表中元素删除的实现方法.分享给大家供大家参考,具体如下: 该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析: 一.图示删除逻辑 假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点. 1.初始时变量prev指向虚拟头结点dummyHead: 2.寻找到前置节点位置,(对于该例子前置节点为索引为1

  • Java实现链表中元素的获取、查询和修改方法详解

    本文实例讲述了Java实现链表中元素的获取.查询和修改方法.分享给大家供大家参考,具体如下: 本节是在上一小节Java链表中添加元素的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素.查询元素以及修改元素进行学习. 一.获取元素 1.关于获取链表中元素的方法的分析 由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下: //获取链表的第index(0-based)个位置的元

  • C++实现LeetCode(141.单链表中的环)

    C++实现LeetCode(141.单链表中的环)

    [LeetCode] 141. Linked List Cycle 单链表中的环 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.

随机推荐