python单链表逆序

如何把一个单链表进行反转？

方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。

方法2：使用3个指针遍历单链表，逐个链接点进行反转。

方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

方法4: 递归(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)

开辟辅助数组，新建表头反转，就地反转，递归反转

# -*- coding: utf-8 -*-

'''

链表逆序

'''

class ListNode:

def __init__(self,x):

self.val=x

self.next=None

'''

第一种方法：

对于一个长度为n的单链表head,用一个大小为n的数组arr储存从单链表从头

到尾遍历的所有元素，在从arr尾到头读取元素简历一个新的单链表

时间消耗O(n),空间消耗O(n)

'''

def reverse_linkedlist1(head):

if head == None or head.next == None: #边界条件

return head

arr = [] # 空间消耗为n,n为单链表的长度

while head:

arr.append(head.val)

head = head.next

newhead = ListNode(0)

tmp = newhead

for i in arr[::-1]:

tmp.next = ListNode(i)

tmp = tmp.next

return newhead.next

'''

开始以单链表的第一个元素为循环变量cur,并设置2个辅助变量tmp,保存数据;

newhead,新的翻转链表的表头。

时间消耗O(n),空间消耗O(1)

'''

def reverse_linkedlist2(head):

if head == None or head.next == None: #边界条件

return head

cur = head #循环变量

tmp = None #保存数据的临时变量

newhead = None #新的翻转单链表的表头

while cur:

tmp = cur.next

cur.next = newhead

newhead = cur # 更新 新链表的表头

cur = tmp

return newhead

'''

开始以单链表的第二个元素为循环变量，用2个变量循环向后操作,并设置1个辅助变量tmp,保存数据;

时间消耗O(n),空间消耗O(1)

'''

def reverse_linkedlist3(head):

if head == None or head.next == None: #边界条件

return head

p1 = head #循环变量1

p2 = head.next #循环变量2

tmp = None #保存数据的临时变量

while p2:

tmp = p2.next

p2.next = p1

p1 = p2

p2 = tmp

head.next = None

return p1

'''

递归操作，先将从第一个点开始翻转转换从下一个节点开始翻转

直至只剩一个节点

时间消耗O(n),空间消耗O(1)

'''

def reverse_linkedlist4(head):

if head is None or head.next is None:

return head

else:

newhead=reverse_linkedlist4(head.next)

head.next.next=head

head.next=None

return newhead

def create_ll(arr):

pre = ListNode(0)

tmp = pre

for i in arr:

tmp.next = ListNode(i)

tmp = tmp.next

return pre.next

def print_ll(head):

tmp = head

while tmp:

print tmp.val

tmp=tmp.next

a = create_ll(range(5))

print_ll(a) # 0 1 2 3 4

a = reverse_linkedlist1(a)

print_ll(a) # 4 3 2 1 0

a = reverse_linkedlist2(a)

print_ll(a) # 0 1 2 3 4

a = reverse_linkedlist3(a)

print_ll(a) # 4 3 2 1 0

a = reverse_linkedlist4(a)

print_ll(a) # 0 1 2 3 4

到此这篇关于用python介绍4种常用的单链表翻转的方法小结的文章就介绍到这了,更多相关python 单链表翻转内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！