Monday, January 5, 2015

Reverse Linked List II (LeetCode Linked List)

Question: 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.

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