java :: reverse list 2 :: in-place and one pass O(n) solution


  • 0
    A
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
       
    	// t refers the node before the slice at m
    	// e refers the node before the slice at n
    	// s refers the node after the slice at m
    	// f refer the node after the slice at n
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(head==null || head.next==null) return head;
            ListNode t=new ListNode(-1),f=new ListNode(-2),s=new ListNode(-1),c=new ListNode(-3),e=new ListNode(-4);
            ListNode dum=new ListNode(-1);
            dum.next=head;
            c=dum;
            for(int i=0;i<=n;i++){
            	if(i==m-1){ // dummy node, incase m=1, will help in slicing out head.
             		t=dum;
            		s=dum.next;
            	}
            	if(i==n){ // slice at nth node. 
            		e=dum; 
            		f=dum.next;
            	}
            	dum=dum.next; 
            }
            // following two lines slice the list in three parts: start to t, s to e, and f to end
            t.next=null;
            e.next=null;
            // reverse reverses s to e part of the list
            reverse(null,s); 
            // re-assign to rest of the list
            t.next=e;
            s.next=f;
            return c.next;
        }
    
        void reverse(ListNode pre,ListNode curr){
    		ListNode next=curr.next;
        	curr.next=pre;
        	if(next!=null) reverse(curr,next);
        }
    
    }
    
    1. mark the necessary references and slice it out.
    2. perform the reversal
    3. reassign it back to the list.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.