My straight-forward Java solution without recursion or dummy nodes (0ms)


  • 20
    • The idea is straightforward: use two pointers and swap
    • a.next = b.next, b.next = a.
    • Then continue the next pair, b = a.next.next, a=a.next
    • Remember to check null
    • Remember to track new head
    • Remember to link the new pair after the prior nodes.

    Attached is the accepted code.

    public class Solution {
      public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode newHead = head.next, a=head,b=a.next,pre = null;
        while(a!=null && b!=null){
          a.next = b.next;
          b.next = a;
          if(pre!=null) pre.next = b;
          if(a.next==null) break;
          b = a.next.next;
          pre = a;
          a = a.next;
        }
        return newHead;
      }
    }
    
    • AC, 0ms

  • 0
    J

    Thank you for your solution!!!


  • 1
    L

    this line: while(a!=null && b!=null){

    I don't think the a!= null is really needed, as long as the b is not null, a != null should be met as well.


  • 4
    C
      b = a.next.next;
      a = a.next;
    

    with changing sequence, this can be written as

      a = a.next;
      b = a.next;
    

  • 0
    C

    @crowdy pre store to complete b->a->d->c , seem not to change the order of ‘a,b’


  • 0
    M

    Your logic is genius. Amazing!


  • 0
    M

    Thanks very much


  • 0
    A

    @YuTingLiu why you use this condition if(pre!=NULL) pre->next=b;


  • 0
    N
    class Solution {
        public ListNode swapPairs(ListNode head) {
            
            if(head == null || head.next == null) return head;
            
    
    		ListNode ret = null;
    		if (head == null || head.next == null)
    			return head;
    		ListNode p = head;
    		ListNode c = null;
    		ListNode t = null;
    
    		while (p != null && p.next != null) {
    			c = p.next;
    			p.next = c.next;
    			c.next = p;
    			if (t != null)
    				t.next = c;
    			else
    				ret = c;
    			t = p;
    
    			p = p.next;
    		}
    
    		return ret;
    	
        }
    }
    

  • 0
    I

    @YuTingLiu hi,your code is very good,but i can not understand the "pre" in your code. how it works . i guess it connects the a to b ,but in the linkedlist we have already know the connect between the two nodes.


Log in to reply
 

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