0092.md

Reverse Linked List II

题目

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

思路

part1: 找出需要翻转的第一个结点reverseBegin以及前一个结点begin
part2：翻转m到n的结点。同时保存需要翻转的最后一个结点reverseEnd以及下一个结点end
part3：正确连接上

注意：加入链表头结点处理特殊情况可以使代码更简洁

代码

迭代

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || head.Next == nil || m==n {
        return head
    }
    newHead := &ListNode{
        Next: head,
    }
    var begin, end, reverseBegin, reverseEnd *ListNode
    cur := newHead
    for i := 1; i < m; i++ {
        cur = cur.Next
    }
    begin, reverseBegin = cur, cur.Next
    cur = cur.Next
    prev := begin
    for i := m; i <= n; i++ {
        if i == n {
            reverseEnd = cur
        }  
        temp := cur.Next
        cur.Next = prev
        prev = cur
        cur = temp
    }
    end = cur
    begin.Next, reverseBegin.Next = reverseEnd, end
    return newHead.Next
    
}