首页 > 代码库 > [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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn 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