Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.
public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { // Start typing your Java solution below // DO NOT write main() function if(head==null || head.next == null) return head; ListNode prev = new ListNode(0); prev.next=head; head=prev; ListNode n1=head; int k=m-1; while(k>0){ n1=n1.next; k--; } prev=n1; n1=n1.next; k=n-m; while(n1.next!=null && k>0){//swap n1 with n1.next ListNode temp = n1.next; n1.next = temp.next; temp.next = prev.next; prev.next =temp;//prev -> temp -> n1 k--; } return head.next; } }
//procedure:
1 -> 2 -> 3 -> 4 -> 5
1 -> 3 -> 2 -> 4 -> 5
1 -> 4- > 3 -> 2 -> 5
mistake: forget the distance between m and n
learned: when do swap, make sure use list(0) to be head // find prev position, first find m-1 then ,the pos is prev