1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Swap Nodes in Pairs
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/swap-nodes-in-pairs/
7+ Notes:
8+ Given a linked list, swap every two adjacent nodes and return its head.
9+ For example,
10+ Given 1->2->3->4, you should return the list as 2->1->4->3.
11+ Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
12+
13+ Solution: 1. Iterative solution with constant space.
14+ 2. Recursive solution with O(n) space (for practice).
15+ */
16+
17+ /**
18+ * Definition for singly-linked list.
19+ * public class ListNode {
20+ * int val;
21+ * ListNode next;
22+ * ListNode(int x) {
23+ * val = x;
24+ * next = null;
25+ * }
26+ * }
27+ */
28+ public class Solution {
29+ public ListNode swapPairs_1 (ListNode head ) {
30+ if (head ==null ||head .next ==null )return head ;
31+ ListNode dummy =new ListNode (0 );
32+ dummy .next =head ;
33+ ListNode cur =dummy ;
34+ while (cur .next !=null &&cur .next .next !=null ) {
35+ ListNode node =cur .next .next ;
36+ cur .next .next =node .next ;
37+ node .next =cur .next ;
38+ cur .next =node ;
39+ cur =node .next ;
40+ }
41+ return dummy .next ;
42+ }
43+ public ListNode swapPairs (ListNode head ) {
44+ if (head ==null ||head .next ==null )return head ;
45+ ListNode first =head ,second =head .next ;
46+ first .next =second .next ;
47+ second .next =first ;
48+ first .next =swapPairs (first .next );
49+ return second ;
50+ }
51+ }
