1+ package Algorithms .list ;
2+
3+ import Algorithms .algorithm .others .ListNode ;
4+
5+ /**
6+ * Definition for singly-linked list.
7+ * public class ListNode {
8+ * int val;
9+ * ListNode next;
10+ * ListNode(int x) {
11+ * val = x;
12+ * next = null;
13+ * }
14+ * }
15+ */
16+ public class SwapPairs3 {
17+ // Solution 1: the recursion version.
18+ public ListNode swapPairs1 (ListNode head ) {
19+ if (head ==null ) {
20+ return null ;
21+ }
22+
23+ return rec (head );
24+ }
25+
26+ public ListNode rec (ListNode head ) {
27+ if (head ==null ||head .next ==null ) {
28+ return head ;
29+ }
30+
31+ ListNode next =head .next .next ;
32+
33+ // 翻转后面的链表
34+ next =rec (next );
35+
36+ // store the new head.
37+ ListNode tmp =head .next ;
38+
39+ // reverse the two nodes.
40+ head .next =next ;
41+ tmp .next =head ;
42+
43+ return tmp ;
44+ }
45+
46+ // Solution 2: the iteration version.
47+ public ListNode swapPairs (ListNode head ) {
48+ // 如果小于2个元素，不需要任何操作
49+ if (head ==null ||head .next ==null ) {
50+ return head ;
51+ }
52+
53+ ListNode dummy =new ListNode (0 );
54+ dummy .next =head ;
55+
56+ // The node before the reverse area;
57+ ListNode pre =dummy ;
58+
59+ while (pre .next !=null &&pre .next .next !=null ) {
60+ // The last node of the reverse area;
61+ ListNode tail =pre .next .next ;
62+
63+ ListNode tmp =pre .next ;
64+ pre .next =tail ;
65+
66+ ListNode next =tail .next ;
67+ tail .next =tmp ;
68+ tmp .next =next ;
69+
70+ // move forward the pre node.
71+ pre =tmp ;
72+ }
73+
74+ return dummy .next ;
75+ }
76+
77+ // Solution 3: the iteration version.
78+ public ListNode swapPairs3 (ListNode head ) {
79+ // 如果小于2个元素，不需要任何操作
80+ if (head ==null ||head .next ==null ) {
81+ return head ;
82+ }
83+
84+ ListNode dummy =new ListNode (0 );
85+ dummy .next =head ;
86+
87+ // The node before the reverse area;
88+ ListNode pre =dummy ;
89+
90+ while (pre .next !=null &&pre .next .next !=null ) {
91+ ListNode next =pre .next .next .next ;
92+
93+ ListNode tmp =pre .next ;
94+ pre .next =pre .next .next ;
95+ pre .next .next =tmp ;
96+
97+ tmp .next =next ;
98+
99+ // move forward the pre node.
100+ pre =tmp ;
101+ }
102+
103+ return dummy .next ;
104+ }
105+ }