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

发布时间：2020-12-14 01:52:17 所属栏目：Linux 来源：网络整理

导读：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? ? 解决思路：使用原地改

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). 流程图如下：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!