给定一个单链表,将其反转。其实很容易想到,只需要修改每个结点的指针指向:即令后一个结点指向前一个结点,并且将表头指针指向最后一个结点即可。
这个过程可以用循环实现,也可以用递归来实现。
1、用循环来实现:
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
|
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、用递归来实现:
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
|
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 |
以下是图解递归的详细过程:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_34840129/article/details/80776363