【LeetCode每天一题】Reverse Linked List(链表反转)

超、凢脫俗 2021-12-15 14:17 208阅读 0赞

Reverse a singly linked list.

Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解决思路：使用原地改变链表的指针进行反转。时间复杂度为O(n)，空间复杂度为O(1). 流程图如下：

　　　　 1639597-20190323164352747-1154750791.jpg

　　　

  1. 1 class Solution(object): 2     def reverseList(self, head): 3         """
  2.  4 :type head: ListNode 5 :rtype: ListNode 6         """
  3.  7         pre = None   # 定义前驱节点
  4.  8         cur = head   # 定义后驱节点
  5.  9         while cur:     # 当cur为空时，循环结束
  6. 10             tem = cur.next       # 使用临时变量保存下一个节点
  7. 11             cur.next = pre       # 指向前驱节点
  8. 12             pre = cur            # 前驱节点复制到当前节点
  9. 13             cur = tem            # 临时变量进行复制
  10. 14         return pre

转载于:https://www.cnblogs.com/GoodRnne/p/10584541.html

发表评论

表情：
评论列表 （有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读