My simple JAVA solution for share


  • 120
    T
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            first.next = second.next;
            current.next = second;
            current.next.next = first;
            current = current.next.next;
        }
        return dummy.next;
    }

  • 1
    I

    The use of dummy node is excellent, thanks!


  • 1
    L

    great. I handle the first two specially. My solution is not beautiful.


  • 38
    R

    I am newbie, so helping other newbies.
    I have explained the solution with inline comments,

    public class Solution {
    public ListNode swapPairs(ListNode head) {
        
        if (head == null) {
            return null;
        }
        ListNode newhead = new ListNode(-1);//dummy
        newhead.next = head;
        ListNode temp = newhead;
        
        ListNode one = null;
        ListNode two = null;
        
        // {dummy->1->2->3->4->null}
        //explanation for one loop rest are same.
        
        
        while(temp.next!= null && temp.next.next!=null) {
            // temp points to dummy in the beginning.
            // one -> 1
            one = temp.next;
            //two -> 2
            two = temp.next.next;
            // 1-> = 2.next = 3;
            one.next=two.next;
            // 2-> = 1
            two.next = one;
            //now dummy should point to 2
            //if the below is not done dummy->1;
            temp.next = two;
            // temp was pointing to dummy
            //temp->1 
            temp = one;
            
            // now { dummy->2->1->3->4 } 
            
        }
        return newhead.next;
    }
    

    }


  • 5

    This is the correct answer using iteration for constant space.


  • 2
    Y

    Same thought.

    public ListNode swapPairs(ListNode head) {
        ListNode virtual = new ListNode(0);
        virtual.next = head;
        ListNode p = head;
        ListNode pre = virtual;
        while (p != null && p.next != null) {
            pre.next = p.next;
            pre = p;
            p = p.next.next;
            pre.next.next = pre;
        }
        pre.next = p;
        return virtual.next;
    }

  • 1
    F

    Great one, mine is messy due to the order...

    public ListNode swapPairs(ListNode head) {
        if (head == null)  return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
    
        while(head != null && head.next != null && head.next.next != null) {
          ListNode first = head.next;
          ListNode third = head.next.next.next;
          head.next = head.next.next;
          head.next.next = first;
          first.next = third;
          head = first;
        }
    
        return dummy.next;
      }

  • 0

    easily understand


  • 0
    S

    i have the same iedal with you.However,your code is better than mine.


  • 0
    T

    @ravi2 Thanks for the explanation. It was easier to understand!!!


  • 0
    L
    public class Solution {
        public ListNode swapPairs(ListNode head) {
            ListNode start=new ListNode(0);
            start.next=head;
            ListNode pre=start;
            while(head!=null && head.next!=null){
                ListNode after=head.next.next;
                pre.next=head.next;
                pre.next.next=head;
                pre=head;
                head=after;
            }
            return start.next;
        }
    }
    

    Why my answer is Time Limit Exceeded? I don't think there is any difference


  • 0
    T

    @lionellijian I believe you shouldn't refer to the head node directly. Try to refer to the head by using the pre node (ListNode pre = start; ). Therefore, instead of using while(head != null && head.next != null) etc... use while (pre.next != null && pre.next.next != null). I hope that will solve your issue.


  • 0
    L

    @thestonx Thanks, Would you please detail the mistake I have made.Why would refer to head directly will cause this problem?


  • 0
    T

    @lionellijian honestly at this point I don't know. I'm doing some research regarding it. As soon as i figure it out I'll let you know. But if you do before me please let me know. At the moment I'm suspecting it to be memory reference related.


  • 0
    L

    @thestonx I have found my mistake. And in fact, I don't need to make change as you said, but add one more line code as below:

    public class Solution {
        public ListNode swapPairs(ListNode head) {
            ListNode start=new ListNode(0);
            start.next=head;
            ListNode pre=start;
            while(head!=null && head.next!=null){
                ListNode after=head.next.next;
                pre.next=head.next;
                // Time limit exceeded without this line below.
                //will always be changed and meaningless, but when it comes to the last pair, it is usable.
                head.next=head.next.next;
                pre.next.next=head;
                pre=head;
                head=after;
            }
            return start.next;
        }
    }
    

    Add [ head.next=head.next.next]
    Because When it comes to last pair, its nextNode's reference will stuck in a infinite loop


  • 0
    T

    @lionellijian it looks like I wasn't of any help and that I was wrong about your reference to the head directly causing the "Time Limit Exceeded error message." I'm glad you figured it out tho.


  • 0
    C

    @ravi2 thk u!


  • 1

    Draw a picture on paper will help a lot for List problem.

        // O(N): prev->first->second => prev->second->first, then move prev to first to maintain invariant
        // invariant: nodes behind prev (inclusive) are swapped already
        public ListNode swapPairs(ListNode head) {
            if (head == null) return null;
            ListNode dmy = new ListNode(0), prev = dmy;
            dmy.next = head;
            while (prev.next != null && prev.next.next != null) {
                ListNode first = prev.next;
                prev.next = first.next;
                first.next = first.next.next;
                prev.next.next = first;
                prev = prev.next.next;
            }
            return dmy.next;
        }
    

  • 0
    K

    @cdai yea, same solution

        public ListNode swapPairs(ListNode head) {
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = dummyHead;
            while (cur.next != null && cur.next.next != null) {
                ListNode curNext = cur.next;
                cur.next = curNext.next;
                curNext.next = cur.next.next;
                cur.next.next = curNext;
                cur = curNext;
            }
            return dummyHead.next;
        }
    

  • 0
    A

    @ravi2 I loved your solution! Thanks for the help!


Log in to reply
 

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