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.

解题方法

这一个的关键是在写loop的时候的终止条件判断。

• 首先找到第n-1个和第m+1个Node, 这里的条件判断比较简单
• 然后reverse nth to mth, 这其间有m-n+1个node，所以p从0开始，终止条件应该是while p <= n - m and cur is not None

Solution

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return None
        if m == n:
            return head

        dummy = ListNode(0)
        dummy.next = head

        p = 1
        preM = dummy
        while p < m:
            preM = preM.next
            p += 1
        # now preM points to m - 1th node
        mth = preM.next

        if not mth:
            return dummy.next

        p = 1
        preN = dummy
        while p <= n:
            preN = preN.next
            p += 1
        # now preN points to n - 1th node
        nth = preN
        afterN = nth.next

        pre = afterN
        cur = mth
        p = 0
        # reverse between
        while p <= n - m and cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
            p += 1

        preM.next = pre

        return dummy.next

Reference