Took 4ms.. in C++ .. Can we improve better?


  • 0
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *reverseBetween(ListNode *head, int m, int n) {
        int count = 1 ;
    	ListNode *temp = NULL , *nextNode = NULL , *current = head , *leftm = NULL;
    	if(head->next == NULL)
    		return head;
    
    	if(m == n)
    		return head;
    
    	while(count <= n){
    		if(count >= m && count <= n ){
    			nextNode = current->next;
    			current->next = temp;
    			temp = current;
    			current = nextNode;
    		} else {
    		if(count == m-1)
    			leftm = current;
    		current = current->next;
    		}
    		
    		count++;
    	}
    
    	if(leftm){
    		leftm->next->next = current;
    		leftm->next = temp;
    	} else {
    	    head->next = current;
    	    return temp;
    	}
    
    	return head;
    
        }
    };
    

    My solution is O(n)


  • 0
    E

    Mine also took 4ms. Just a little bit shorter:

    class Solution {
    public:
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            ListNode ** sub_head = &head;
            ListNode * oper0 = head, * oper1 = head, * oper2 = head; 
            for (int i =0; i < m-1; i++) {
                sub_head = &((*sub_head)->next);
            }
            oper0 = *sub_head;
            oper1 = oper0;
            oper2 = oper1->next;
            for( int i = 0; i < n-m; i++) {
                oper0 = oper1;
                oper1 = oper2; 
                oper2 = oper2->next;
                oper1->next = oper0; 
                }
            (*sub_head)->next = oper2;
            *sub_head = oper1;
            return head;
        }
    };

Log in to reply
 

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