92.md

92. 反转链表 II

https://leetcode-cn.com/problems/reverse-linked-list-ii

Solution

Swift

func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
    guard let h = head else {
        return nil
    }
    
    let fake = ListNode(110)
    fake.next = h
    
    // A + B + C
    var aTail: ListNode? = fake
    var bHead: ListNode? = fake.next
    var bTail: ListNode? = bHead
    
    var index = 0
    while index+1 < m {
        aTail = aTail?.next
        bHead = aTail?.next
        bTail = bHead
        index += 1
    }
    
    var reversedList: ListNode? = nil   // 已翻转的链表
    var current: ListNode? = bHead      // 当前节点
    var next: ListNode? = current?.next     // 下一个节点
    
    while index < n {
        // 更新已翻转链表
        current?.next = reversedList
        reversedList = current
        
        // 更新 current next 节点
        current = next
        next = current?.next
        
        index += 1
    }
    
    aTail?.next = reversedList
    bTail?.next = current

    return fake.next
}

Tip

• 局部翻转链表