For this problem, the basic idea is to move the mth node in the linked list right behind the nth node, i.e. "8". One thing to notice is that every time one node is moved, we always pick the node after the (m-1) th node, and move it behind that node "8". Since node "8" should be moved forward, it is wrong to keep moving the mth node behind nth node, which should be not node "8" any more.
In my solution, variable preNNode might be unnecessary. The following code can be improved later.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null|| m > n || m <= 0 || n <= 0) return null;
if (m == n) return head;
int preMIdx = m - 1;
int preNIdx = n - 1;
ListNode preMNode = head;
ListNode preNNode = head;
ListNode mNode = head;
ListNode nNode = head;
if(preMIdx == 0){// In this case, m is 1
nNode = preNNode.next;
int i = 1;
while(i < n - 1 && preNNode != null && nNode != null){
preNNode = preNNode.next;
nNode = nNode.next;
i++;
}
if(preNNode == null || nNode == null){
return null;
}
// ListNode insertAfterNode = nNode;
while(head != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
mNode = head.next;
// preMNode.next = mNode.next;
head.next = nNode.next;
nNode.next = head;
head = mNode;
// insertAfterNode = insertAfterNode.next;
}
}
else{
mNode = preMNode.next;
int i = 1;
while(i < m - 1 && preMNode != null && mNode != null){
preMNode = preMNode.next;
mNode = mNode.next;
i ++;
}
if(preMNode == null || mNode == null){
return null;
}
nNode = preNNode.next;
i = 1;
while(i < n - 1 && preNNode != null && nNode != null){
preNNode = preNNode.next;
nNode = nNode.next;
i ++;
}
if(preNNode == null || nNode == null){
return null;
}
// ListNode insertAfterNode = nNode;
while(preMNode.next != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
preMNode.next = mNode.next;
mNode.next = nNode.next;
nNode.next = mNode;
mNode = preMNode.next;
// preMNode = preMNode.next;
// insertAfterNode = insertAfterNode.next;
}
}
return head;
}
}
Hello, welcome to Yizhe's Blog. I am Yizhe Liu, graduated from University of Arizona, with Master degree, major in Electrical and Computer Engineering. Actually, I am software guy. In my blog, many posts are about the Leetcode questions. I will post my ideas and implementations, which are accepted by Leetcode. If you have different opinions, please leave comment. I am happy to discuss with you. So lets start rocking them!!!
No comments:
Post a Comment