4ms Java Solution-swap values instead of nodes in pairs


  • 0
    L

    Your runtime beats 80.06% of java submissions.

    55 / 55 test cases passed.
    Status: Accepted
    Runtime: 4 ms

    public class Solution {
        public ListNode swapPairs(ListNode head) {
            if( head == null) return head;
            ListNode dummyHead = head;
    
            while(head!=null && head.next!=null) {
                swap(head, head.next);
                head= head.next.next;
            }
    
            return dummyHead;
        }
    
        private void swap(ListNode n1, ListNode n2) {
            int tmp = n1.val;
            n1.val = n2.val;
            n2.val = tmp;
        }
    }
    

  • 0
    S

    According to the question:

    Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
    

  • 1
    L

    Thanks for pointing out the issue. I made a correction below by swapping the links instead of values. The execution time is still 4ms.

    public ListNode swapPairs(ListNode head) {
            if( head == null || head.next == null) return head;
    
            ListNode dummyHead = new ListNode(0);
            dummyHead.next  = head;
            head = swap(dummyHead);
    
            while(head!=null ) {
                head = swap(head);
            }
    
            return dummyHead.next;
        }
    
        private ListNode swap(ListNode head) {
            if( head.next == null || head.next.next == null ) {
                return null;
            }
    
            ListNode n1 = head.next;
            ListNode n2 = n1.next;
            ListNode n3 = n2.next;
    
            head.next =n2;
            n2.next = n1;
            n1.next = n3;
    
            return n1;
        }
    

    Here is the diagram to show how it works:
    0_1479059367836_SwapNodesInPairs.jpeg


Log in to reply
 

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