[leetcode] Reverse Linked List 2 | 把单链表第m~n个给inplace反转其他不变
Posted by: lexigrey on: October 11, 2013
原来反转单链表有另一种简洁的做法,看来每道题过了之后一定还得看别人答案才行,这才能做到“做的多了就会了”。
- 比如反转b->c->d:a->b->c->d->e => a->d->c->b->e
- 三个variable
- prevM:指向反转部分的前一个元素a
- prev:指向已经反转成功的最后一个元素,永远是prevM.next,不需要改动。
- 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
Leave a Reply