python递归&迭代方法实现链表反转

定义链表node结构：

class ListNode:

  def __init__(self,data):
    self.data = data
    self.next = None

将L转化为链表：

def make_list(L):

将L初始化为链表：

 head = ListNode(L[0])
  cur = head
  for i in L[http://www.cppcns.com1:]:
    cur.next = ListNode(i)
    cur = cur.next
  return head

遍历链表：

def print_list(head):

  cur = head
  while cur != None:
    print(cur.data,end=' ')
    cur = cur.neZIZOOmvQxt

递归法  反转链表：

def reverse_list(head):

三要素：

• 1.明确函数功能，该函数可以将链表反转，并返编程客栈回一个头节点
• 2.结束条件：当链表为空或只有一个节点时返回

  if head==None or head.next==None:
    return head

• 3.等价条件（缩小范围），对于数组来讲，缩小范围是n——>n-1，对于链表来讲则可以考虑head——

>head.next
  reverse = reverse_list(head.next) #假设reverse是head以后的、已经反转过的链表

接下来要做的是将head节点接到已经反转过的reverse上：

  tmp = head.next
  tmp.next = head
  head.next = None
return reverse #返回新的列表

迭代法：

def reverse_list2(head):
  #print_list编程客栈(head)
  cur = head
  pre = None
  while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
  head = pre
  return head

if __name__ == '__main__':

  L = [3,2,7,8]
  head = make_list(L)

正序打印：

  print('原始list：')
  print_list(head)
  print('\n')

反转后打印：

  revere = reverse_list(head)
  print('反转一次的list：')
  print_list(revere)
  print('\n')

反转2：

  print('head is')
  print_list(head) #发现此时head节点变成了最后一个节点，说明http://www.cppcns.com函数是对head这个实例直接作用的
  print('\n')

  # print('revere is')
  # print_list(revere)
  # print('\n')

  print('反转两次的list：')
  print_list(reverse_list2(revere))

到此这篇关于python递归&迭代方法实现链表反转的文章就介绍到这了,更多相关python链表反转内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！