Lexi's Leetcode solutions

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

Posted on: October 11, 2013

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

  • 比如反转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:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 221,510 hits
October 2013
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031  
%d bloggers like this: