描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

Python

注释很详细

class Solution:
    def reverseBetween(self, head, m, n):

        if m==n:
            return head
        # Consider linked list as a list A. i.e. A[1]=head.val, A[2]=head.next.val ....
        # Create dummy.         [D,A[1],A[2],....]        
        dummy=ListNode(0)
        dummy.next=head
        # c at A[0]
        c=dummy

        # move c m-1 times. now c is at A[M-1]
        for _ in range(m-1):
            c=c.next

        # start reversing from s=c.next (A[M]) for n-m+1 nodes
        s,r=c.next,None
        for _ in range(n-m+1):
            s.next,s,r=r,s.next,s

        # now the situation is
        # [dummy .... c]    [r,..., c.next]   [s .....]
        # connect c to r, and c.next to s


        # careful. c.next,c.next.next=r,s gives you an error
        c.next.next,c.next=s,r

        return dummy.next