Python数据结构之翻转链表,python数据结构翻转
Python数据结构之翻转链表,python数据结构翻转
翻转一个链表
样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null
一种比较简单的方法是用“摘除法”。就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点。
那样例来说,步骤是这样的:
1. 新建空节点:None
2. 1->None
3. 2->1->None
4. 3->2->1->None
代码就非常简单了:
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): temp = None while head: cur = head.next head.next = temp temp = head head = cur return temp # write your code here
当然,还有一种稍微难度大一点的解法。我们可以对链表中节点依次摘链和链接的方法写出原地翻转的代码:
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): if head is None: return head dummy = ListNode(-1) dummy.next = head pre, cur = head, head.next while cur: temp = cur # 把摘链的地方连起来 pre.next = cur.next cur = pre.next temp.next = dummy.next dummy.next = temp return dummy.next # write your code here
需要注意的是,做摘链的时候,不要忘了把摘除的地方再连起来
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关内容
- Python 数据结构之旋转链表,python数据结构
- 利用python程序生成word和PDF文档的方法,
- python用装饰器自动注册Tornado路由详解,pythontornado
- python 出现SyntaxError: non-keyword arg after keyword arg错误解决
- 深入理解Python对Json的解析,深入理解pythonjson
- 关于Python面向对象编程的知识点总结,python面向对象编
- Python变量和数据类型详解,python变量数据类型
- Python错误提示:[Errno 24] Too many open files的分析与解决,
- 使用PyV8在Python爬虫中执行js代码,pyv8python
- python字符串中的单双引,python字符串单双引
评论关闭