## Cod24. 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's post)

Code: Recursively swaping every pairs

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

class Solution(object):
"""
:rtype: ListNode
"""

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):
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

``````/**
* 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;
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;
}
}
``````