LeetCode: Reverse Linked List II

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.

Solution:
At first I misunderstood the problem. I thought it requires to exchange the mth and the nth node. The code is as follows

	public ListNode reverseBetweenTwoNodes(ListNode head, int m, int n) {
	if(m==n) return head;
	if(head.next==null) return head;
	ListNode node = head, prv = head;
	ListNode mNode = head, mPrv =head;
	int i=1;
	if((m+1) == n){//at first, I didn't consider this situation.
	while(node != null){
	if(i==m){
	if(m==1){
	node=head.next;
	ListNode tempNext = node.next;
	node.next = head;
	head.next = tempNext;
	head = node;
	}
	else{
	ListNode tempNext = node.next.next;
	prv.next = node.next;
	node.next.next = node;
	node.next = tempNext;
	}
	break;
	}
	i++;
	prv = node;
	node = node.next;
	}
	}
	else{
	while(node != null){///while(node) wrong several times
	if(i==m){
	mNode = node;
	mPrv = prv;
	}
	else if(i==n){
	if(m==1){
	head = head.next;
	prv.next = mNode;
	mNode.next = node.next;
	node.next = head;
	head = node;
	}
	else{
	mPrv.next=node;
	prv.next = mNode;
	ListNode tempNext = node.next;
	node.next = mNode.next;
	mNode.next = tempNext;
	}
	break;
	}
	i++;
	prv = node;
	node = node.next;
	}
	}
	return head;//forgot the return statement
	}

view raw gistfile1.java hosted with ❤ by GitHub

The real intention of this problem is to reverse all nodes between the mth and the nth node. Code:

	public ListNode reverseBetween(ListNode head, int m, int n) {
	if(m==n) return head;
	if(head.next==null) return head;
	ListNode node = head, prv = head;
	ListNode insertRight = head, insertLeft =head;
	int i=1;
	ListNode tempHead = new ListNode(0);
	//use a dumb node to be the temp head if m==1. the trick saves code to deal with the special case of head
	while(node != null){
	if(i==m){
	if(m==1) insertLeft = tempHead;
	else insertLeft = prv;
	insertRight = node;
	}
	if(i>m){
	prv.next = node.next;
	insertLeft.next = node;
	node.next = insertRight;
	insertRight = insertLeft.next;
	node = prv;//for next node to be picked up and inserted
	}
	i++;
	if(i>n) break;
	prv = node;
	node = node.next;
	}
	if(tempHead.next != null) return tempHead.next;
	else return head;
	}

view raw gistfile1.java hosted with ❤ by GitHub