O(n) time complexity solution. Two cycles. O(1) space complexity;


  • 0
    O
    
            if (head == null || head.next == null) {
                return head;
            }
            ListNode odd  = head, tmp;
            ListNode even = null; 
            ListNode evenTmp = even;
            int i = 1;
            while(odd != null && odd.next != null) {
        		tmp = odd.next;
        		odd.next = tmp.next;
        		tmp.next = null;
        		if (even == null) {
        			even = tmp;
        			evenTmp = even;
        		} else {
        			evenTmp.next = tmp;
        			evenTmp = evenTmp.next;
        		}
            	odd = odd.next;
            }
            tmp = head;
            while(tmp.next != null) {
            	tmp = tmp.next;
            }
            tmp.next = even;
            
            return head;
        }
    

Log in to reply
 

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