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