面试高频：反转链表
反转一个单链表
输入一个链表，反转链表后，输出新链表的表头。
1. python的非递归实现
思路很简单：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。
def reverseList(self, head: ListNode) -> ListNode:
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev2.python的递归实现
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。
注意关于链表问题的常见注意点的思考：
1、如果输入的头结点是 NULL，或者整个链表只有一个结点的时候
2、链表断裂的考虑
def reverseList(self, head: ListNode) -> ListNode:
if head == None or head.next == None: return head
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHead本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录