Simple five line recursive O(N) solution and Constant Space iterative solution


  • 0
    M

    Recursive solution. O(N) space and time complexity

        public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null){return head;}
            ListNode nextNode = head.next, save = head.next.next;
            nextNode.next = head;
            head.next = swapPairs(save);
            return nextNode;
        }
    

    Iterative solution O(N) time and O(1) space

        public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null){return head;}
            ListNode N1 = head, N2 = head.next, saveHead = N2;
            while(N2 != null){
                ListNode save = N2.next;
                N2.next = N1;
                if(save != null && save.next != null){
                    N1.next = save.next;  
                }else{
                    N1.next = save;
                    break;
                }
                N1 = save; N2 = save.next;
            }       
            return saveHead;
        }
    

Log in to reply
 

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