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

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

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

查看更多关于Python实现单链表中元素的反转的详细内容...