[leetcode] Reverse Linked List 2 | 把单链表第m～n个给inplace反转其他不变

Posted by: lexigrey on: October 11, 2013

• In: leetcode
• Leave a Comment

原来反转单链表有另一种简洁的做法，看来每道题过了之后一定还得看别人答案才行，这才能做到“做的多了就会了”。

• 比如反转b->c->d：a->b->c->d->e => a->d->c->b->e
• 三个variable
  1. prevM：指向反转部分的前一个元素a
  2. prev：指向已经反转成功的最后一个元素，永远是prevM.next，不需要改动。
  3. curr：想往prevM后面塞的那个元素。
• 算法：每次拿出右边的新元素，往prevM后面插，最后curr==不需要反转的section的第一个节点时退出

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevM = dummy, prev, curr;
    for (int i = 1; i <= n; i++) {
        if (i < m) {
            prevM = prevM.next;
        } else if (i == m) {
            prev = prevM.next;
            curr = prev.next;
        }else {
            prev.next = curr.next;
            curr.next = prevM.next;
            prevM.next = curr;
            curr = prev.next;
        }
    }
    return dummy.next;
}

Tags: list