> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/data-structure/linked-list/swap-nodes-in-pairs.md).

# 24. Swap Nodes in Pairs

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.

**Thoughts:**

1. Recusively solve the problem, but O(n) extra space
2. Iteratively: Here,`pre`is the previous node. Since the head doesn't have a previous node, I just use`self`instead. Again,`a`is the current node and`b`is the next node. To go from`pre -> a -> b -> b.next`to`pre -> b -> a -> b.next`, we need to change those three references. Instead of thinking about in what order I change them, I just change all three at once.([StefanPochmann](https://leetcode.com/stefanpochmann)'s [post](https://leetcode.com/problems/swap-nodes-in-pairs/discuss/11019/7-8-lines-C++-Python-Ruby))

**Code: Recursively swaping every pairs**

```python
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next: return head
        n = head.next
        head.next = self.swapPairs(head.next.next)
        n.next = head

        return n
```

**Code: Iteratively** 

```
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        dummy = ListNode(0)
        pre, pre.next = dummy, head
        while pre.next and pre.next.next:
            a = pre.next
            b = pre.next.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return dummy.next
```

**Code: Iteratively**

```java
/**
 * 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.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            first.next = second.next;
            cur.next = second;
            cur.next.next = first;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}
```