Thursday, July 10, 2014

Reverse Linked List II

Given positions m and n in a linked list, reverse all the nodes from mth node to nth node.

 public class Solution {  
   public ListNode reverseBetween(ListNode head, int m, int n) {  
     if (head == null || head.next == null || m == n)  
       return head;  
     ListNode newHead = new ListNode(0);  
     newHead.next = head;  
     ListNode pre = newHead;  
     ListNode first = head, second = head;  
     int further = n > m ? n:m, near = n < m?n:m;  
     for (int i=1; i<=further; i++) {  
       if (i < near)   
         pre = pre.next;  
       else if (i == near) {  
         first = pre.next;  
         second = first.next;  
       }else {  
         first.next = second.next;  
         second.next = pre.next;  
         pre.next = second;  
         second = first.next;  
       }  
     }  
     return newHead.next;  
   }  
 }  

No comments:

Post a Comment