【python面试题】链表反转

发布于:2021-09-26 12:39:36

单链表反转【python实现】
单链表反转方法
头节点开始遍历

    用三个指针来解决链表反转,cur是现在的链表节点,tmp暂存cur.nextnew_head指向之前的cur其中,tmp是保存之前的链条不能断的,很重要

尾节点开始递归
    递归反转链表,递归:从尾节点指向上一级节点,上一级节点指向None,重复这个过程,直到递归结束

代码如下:

class ListNode:

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


class Solution:

def reverse_list(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head

# 用三个指针来解决链表反转,cur是现在的链表节点,tmp暂存cur.next,new_head指向之前的cur
cur = head
tmp = None
new_head = None
while cur:
tmp = cur.next
cur.next = new_head
new_head = cur
cur = tmp

return new_head

def reverse_list2(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
# 通过Node指向之前的head来进行链表反转
Node = None
while head:
p = head
head = head.next
p.next = Node
Node = p
return Node

def reverse_list_recusive(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# 递归反转链表,递归:从下一级的节点指向上一级节点,上一级节点指向None,重复这个过程,直到递归结束
NewHead = self.reverse_list_recusive(head.next)
head.next.next = head
head.next = None
return NewHead


if __name__ == "__main__":
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)

n1.next = n2
n2.next = n3
n3.next = n4

new_head = Solution().reverse_list(n1)
print(new_head.val)
print(new_head.next.val)
print(new_head.next.next.val)
print(new_head.next.next.next.val)

print()

new_head = Solution().reverse_list2(new_head)
print(new_head.val)
print(new_head.next.val)
print(new_head.next.next.val)
print(new_head.next.next.next.val)

print()

new_head = Solution().reverse_list_recusive(new_head)
print(new_head.val)
print(new_head.next.val)
print(new_head.next.next.val)
print(new_head.next.next.next.val)

THE END

? 这道题很经常的出现在各个厂的笔试题和面试题中,*时大家估计很少用链表,但是面试经常考,所以也要注意下链表的性质,和怎么反转链表

相关推荐

最新更新