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

时间:2022-11-13 21:40:51

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

1.循环反转单链表

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

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

代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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.递归实现单链表反转

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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实现代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/u011608357/article/details/36933337