92. Reverse Linked List II

Loading...LeetCode

要reverse指定位置间的node，但链表自身没有index，只能自己来记录index了。

简单的思路是先把当前指针移动m次，到达要reverse的第一个node，然后用 Q206 的方法 reverse 接下来的 m-n 个node，最后再把两头接上。为了应对m=1的情况，最左端需要多连一个node来保证left指针位置有效。

206. Reverse Linked List

或者，用另一种思路去reverse，即遇到第m个node后，记录当前prev[m]，然后不停地把它后面一个元素放到prev[m]的next位置，移动n-m次，也一样实现 reverse 这一段的效果，且简洁许多，不需要考虑 m, n 取值的 edge case.

向前连接reverse

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n: return head
        
        dummy = ListNode(0)
        dummy.next = head
        left = dummy
        for _ in range(m-1): 
            left = left.next
        cur = left.next
        
        right = cur
        for _ in range(n-m+1): 
            right = right.next if right.next else None
        prev = right
        
        for _ in range(n-m):
            follow = cur.next
            cur.next = prev
            prev = cur
            cur = follow
        
        if left: left.next = cur
        cur.next = prev
        
        return dummy.next

定点插入reverse

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = cur = head
        prev = res
        for _ in range(m-1):
            cur = cur.next
            prev = prev.next
        for _ in range(n-m):
            temp = cur.next
            cur.next = temp.next
            temp.next = prev.next
            prev.next = temp
        return dummy.next