# Question

Formatted question description: https://leetcode.ca/all/24.html

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]


Example 2:

Input: head = []
Output: []


Example 3:

Input: head = [1]
Output: [1]


Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

# Algorithm

Create a dummyHead that occurs before head, that is, dummyHead.next = head. Each time take the two next nodes, and modify the next elements that each node points to. Suppose the current node is temp, and the next two nodes are node1 and node2 respectively, that is, node1 = temp.next and node2 = temp.next.next.

If node1 == null or node2 == null, then the end of the list is reached, so stop the process. Otherwise, change the nodes as follows. Let temp.next = node2, node1.next = node2.next, and node2.next = node1. After these steps, node1 and node2 are swapped. Move temp two steps forward (which should point to node1 after moving two steps), and do swapping for the next nodes. Finally, return dummyHead.next.

# Code

• public class Swap_Nodes_in_Pairs {

public static void main(String[] args) {

Swap_Nodes_in_Pairs out = new Swap_Nodes_in_Pairs();
Solution s = out.new Solution();
}

public class Solution {
//			if (head == null) { // this will not pass while loop below
//			}

ListNode dummy = new ListNode(0);

ListNode prev = dummy;

// if only one node left, then no swap
while (prev.next != null && prev.next.next != null) {

ListNode first = prev.next;
ListNode second = first.next;

ListNode third = second.next;

// swap
prev.next = second;
second.next = first;
first.next = third;

prev = prev.next.next;
}

return dummy.next;
}
}
}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy, cur = head;
while (cur != null && cur.next != null) {
ListNode t = cur.next;
cur.next = t.next;
t.next = cur;
pre.next = t;
pre = cur;
cur = cur.next;
}
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/swap-nodes-in-pairs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode h, *tail = &h;
q->next = p;
tail->next = q;
tail = p;
}
return h.next;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
while cur and cur.next:
t = cur.next
cur.next = t.next
t.next = cur
pre.next = t
pre, cur = cur, cur.next
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

pre = None
while cur and k > 0:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
k -= 1
return cur, pre

pre = None
while p:
if pre:
pre = p
p = next
return ret


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
}
return p
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function swapPairs(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next != null && cur.next.next != null) {
const a = cur.next;
const b = cur.next.next;
[a.next, b.next, cur.next] = [b.next, a, b];
cur = cur.next.next;
}
return dummy.next;
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
var swapPairs = function (head) {
const dummy = new ListNode(0, head);
let pre = dummy;
while (cur && cur.next) {
const t = cur.next;
cur.next = t.next;
t.next = cur;
pre.next = t;
pre = cur;
cur = cur.next;
}
return dummy.next;
};


• # Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @return {ListNode}
pre = dummy
while !cur.nil? && !cur.next.nil?
t = cur.next
cur.next = t.next
t.next = cur
pre.next = t
pre = cur
cur = cur.next
end
dummy.next
end

• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut cur = dummy.as_mut().unwrap();
while cur.next.is_some() && cur.next.as_ref().unwrap().next.is_some() {
cur.next = {
let mut b = cur.next.as_mut().unwrap().next.take();
cur.next.as_mut().unwrap().next = b.as_mut().unwrap().next.take();
let a = cur.next.take();
b.as_mut().unwrap().next = a;
b
};
cur = cur.next.as_mut().unwrap().next.as_mut().unwrap();
}
dummy.unwrap().next
}
}