最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Python数据结构之翻转链表
时间：2017-05-03 编辑：简简单单 来源：一聚教程网
翻转一个链表
样例：给出一个链表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 """ classSolution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ defreverse(self, head): temp=None whilehead: cur=head.next head.next=temp temp=head head=cur returntemp # write your code here | |
当然，还有一种稍微难度大一点的解法。我们可以对链表中节点依次摘链和链接的方法写出原地翻转的代码：
| 代码如下 | 复制代码 |
""" Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None): self.val = val self.next = next """ classSolution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ defreverse(self, head): ifheadisNone: returnhead dummy=ListNode(-1) dummy.next=head pre, cur=head, head.next whilecur: temp=cur # 把摘链的地方连起来 pre.next=cur.next cur=pre.next temp.next=dummy.next dummy.next=temp returndummy.next # write your code here | |
需要注意的是，做摘链的时候，不要忘了把摘除的地方再连起来
相关文章
- Python 数据结构之旋转链表 05-03
- PHP导出数据超时的优化建议解读 10-31
- PHP之mysql位运算解析 10-31
- Laravel实现登录跳转功能解析 10-31
- php双向队列解读 10-31
- Laravel异常上下文解决教程 10-24