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.
Idea: First add a dummy head since m may be 1. Then find the node m-1, which is right before the section needed to be reversed. Then for each node from m+1 to n, insert it right after the node m-1. The that section is reversed.
Time: O(n) Space: O(1)
Code:
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m==n)
return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode pre=dummy;
for(int i=0;i<m-1;i++)
pre=pre.next;
ListNode head2=pre;
pre=head2.next;
ListNode cur=pre.next;
for(int i=m;i<n;i++)
{
pre.next=cur.next;
cur.next=head2.next;
head2.next=cur;
cur=pre.next;
}
return dummy.next;
}
}
No comments:
Post a Comment