首页 > 代码库 > [LeetCode] Reverse Linked List II @ Python
[LeetCode] Reverse Linked List II @ Python
原题地址:https://oj.leetcode.com/problems/reverse-linked-list-ii/
题意:
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL
, m = 2 and n = 4,
return 1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
解题思路:翻转链表的题目。请用积木化思维(Building block):
这里必须的积木:链表翻转操作:
current.next, prev, current = prev, current, current.next
代码:
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # @param head, a ListNode # @param m, an integer # @param n, an integer # @return a ListNode def reverseBetween(self, head, m, n): diff, dummy = n - m, ListNode(0) dummy.next = head prev, current = dummy, dummy.next while current and m >1: prev, current = current, current.next m -= 1 last_swapped, first_swapped = prev, current while current and diff >= 0: current.next, prev, current = prev, current, current.next diff -= 1 last_swapped.next, first_swapped.next = prev, current return dummy.next # Reverse partial Linked List # Refer Figure1: http://images.cnitblog.com/i/546654/201404/072244468407048.jpg # Refer: http://www.cnblogs.com/4everlove/p/3651002.html # Refer: http://stackoverflow.com/questions/21529359/reversing-a-linked-list-in-python # 1 --> 2 --> 3 --> 4 --> 5 # # first_swapped.next = current # __________________ # ^ | # | V # 1 2 <-- 3 <-- 4 5 # | ^ # V ________________| # last_unswapped.next=prev
[LeetCode] Reverse Linked List II @ Python
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。