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;
}
My simple JAVA solution for share


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; }
}

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; }

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; }


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

@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.

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

@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.

@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

@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.


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; }

@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; }
