数据结构与算法 —— 链表linked list(05)

反转一个单链表。

进阶:
链表可以迭代或递归地反转。你能否两个都实现一遍?

示例 :

给定这个链表:1->2->3->4->5

返回结果: 5->4->3->2->1

题目链接

解题思路: 1. 迭代版本:

循环列表,定义两个指针,一个指针是已经迭代完的链表的最后一个节点称为last_node,一个指针是已经迭代完的节点的第一个节点称为next_node。

刚开始的时候last_node 和next_node都指向链表head,循环last_node的next节点定义为cur,把last_node的next指向cur的next指针,把cur的next指向next_node节点。

next_node赋值为当前的cur节点。

最后返回next_node即可。

图如下

1   ->2    ->3   ->4   ->5

|

next_node

last_node

循环完1之后

2   ->1    ->3   ->4   ->5

|    |

|      last_node

next_node

代码如下:

# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return None last_node = head next_node = head while (last_node.next): cur = last_node.next cur_next = cur.next cur.next = next_node last_node.next = cur_next next_node = cur return next_node

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwfff.html