24. Swap Nodes in Pairs.md

24. Swap Nodes in Pairs

Question:

Given a linked list, swap every two adjacent nodes and return its head.

Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

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

Thinking:

	class Solution {
	    public ListNode swapPairs(ListNode head) {
	        ListNode result = new ListNode(0);
	        result.next = head;
	        ListNode temp = result;
	        while(temp.next != null && temp.next.next != null){
	            ListNode pre = temp.next;
	            temp.next = pre.next;
	            pre.next = temp.next.next;
	            temp.next.next = pre;
	            temp = temp.next.next;
	        }
	        return result.next;
	    }
	}

二刷

二刷时仍然使用和一刷时一样的方法。保存一些temp结点，在while循环中不断交换结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        dummy.next = head;
        ListNode temp = null;
        ListNode next = null;
        while(cur.next != null && cur.next.next != null){
            temp = cur.next;
            next = cur.next.next.next;
            cur.next = temp.next;
            temp.next = next;
            cur.next.next = temp;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}

Third Time

• Method 1:

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public ListNode swapPairs(ListNode head) {
   		ListNode dummy = new ListNode(0);
   		dummy.next = head;
   		ListNode cur = dummy;
   		while(cur != null && cur.next != null && cur.next.next != null){
   			ListNode temp = cur.next;
   			ListNode next = temp.next.next;
   			cur.next = temp.next;
   			cur.next.next = temp;
   			temp.next = next;
   			cur = cur.next.next;
   		}
   		return dummy.next;
   	}
   }