反转一个单链表。
进阶:
链表可以迭代或递归地反转。你能否两个都实现一遍?
示例 :
给定这个链表: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