LeetCode解題之Reverse Linked List II

原題

在只遍歷一遍且不申請額外空間的情況下將一個鏈表的第m到n個元素進行翻轉。

注意點：

• m和n滿足如下條件：1 ≤ m ≤ n ≤鏈表長度

例子：

輸入: 1->2->3->4->5->NULL, m = 2, n = 4

輸出: 1->4->3->2->5->NULL

解題思路

通過 Reverse Linked List 已經可以實現鏈表的翻轉。看下圖，把要翻轉的一段先進行翻轉，再把它和前后的鏈表接起來。因為可能要把第一個節點也進行翻轉，為了一致性增加一個假的頭節點。

AC源碼

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def to_list(self):
        return [self.val] + self.next.to_list() if self.next else [self.val]


class Solution(object):
    def reverseBetween(self, head, m, n):
        """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """
        dummy = ListNode(-1)
        dummy.next = head
        node = dummy
        for __ in range(m - 1):
            node = node.next
        prev = node.next
        curr = prev.next
        for __ in range(n - m):
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        node.next.next = curr
        node.next = prev
        return dummy.next


if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n5 = ListNode(5)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    r = Solution().reverseBetween(n1, 2, 4)
    assert r.to_list() == [1, 4, 3, 2, 5]

歡迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 來獲得相關源碼。