# Question

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

24	Swap Nodes in Pairs

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

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

*/

/*
could be extended, swap k sublist

eg: k=3, 2->1->4->3->2->1->4->3

2->1->4->3->2->1->4->3  ===>  (2->1->4)->(3->2->1)->4->3  ===>  4->1->2->1->2->3->4->3

then just extract a method of reversing a sublist, and update to next k nodes



# 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

Java

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

• // 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(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: