未加星标

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

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

单链表的反转可以使用循环,也可以使用递归的方式

1.循环反转单链表

循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。

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

代码:

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;
cur=head;
h=head;
while cur:
h=cur;
tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
return h;

head=ListNode(1); #测试代码
p1=ListNode(2); #建立链表1->2->3->4->None;
p2=ListNode(3);
p3=ListNode(4);
head.next=p1;
p1.next=p2;
p2.next=p3;
p=nonrecurse(head); #输出链表 4->3->2->1->None
while p:
print p.val;
p=p.next;

结果:

4
3
2
1
>>>
2.递归实现单链表反转
class ListNode:
def __init__(self,x):
self.val=x;
self.next=None;


def recurse(head,newhead): #递归,head为原链表的头结点,newhead为反转后链表的头结点
if head is None:
return ;
if head.next is None:
newhead=head;
else :
newhead=recurse(head.next,newhead);
head.next.next=head;
head.next=None;
return newhead;

head=ListNode(1); #测试代码
p1=ListNode(2); # 建立链表1->2->3->4->None
p2=ListNode(3);
p3=ListNode(4);
head.next=p1;
p1.next=p2;
p2.next=p3;
newhead=None;
p=recurse(head,newhead); #输出链表4->3->2->1->None
while p:
print p.val;
p=p.next;

运行结果同上。

总结

以上就是本文关于单链表反转python实现代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!


您可能感兴趣的文章:Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】Python数据结构之单链表详解Python单链表简单实现代码Python单链表的简单实现方法python单链表实现代码实例

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

主题: 数据结构反转算法Python数据
tags: head,gt,next,None,ListNode,cur,链表,newhead,单链,p2,self,p1,pre,反转,return
分页:12
转载请注明
本文标题:单链表反转python实现代码示例
本站链接:http://www.codesec.net/view/572645.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(80)