Java 0ms iterative and 1ms recursive


  • 0
    Y

    Note: since it is tail recursion, recursion is not really necessary.

    public class Solution {
        public ListNode swapPairs(ListNode head) {
            return swapPairsIterative(head);
            //return swapPairsRecursive(head);
        }
        
        private ListNode swapPairsRecursive(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode nextnextSwapped = swapPairs(head.next.next);
            ListNode newHead = head.next;
            newHead.next = head;
            head.next = nextnextSwapped;
            return newHead;       
        }
        
        private ListNode swapPairsIterative(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode newHead = head.next;
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null && curr.next != null) {
                ListNode next = curr.next;
                ListNode nextnext = curr.next.next;
                if (prev != null) {
                    prev.next = next;
                }
                next.next = curr;
                //NOTE: without this step, we get infinite loop at the tail
                curr.next = null; 
                prev = curr;
                curr = nextnext;
            }
            //NOTE: for list with odd number of nodes, like 1->2->3, connect 2 and 3
            if (curr != null) { 
                prev.next = curr;
            }
            return newHead;        
        }    
    }

Log in to reply
 

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