给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
方法一： 递归
- 确定递归的参数
- 终止条件
- 调用单元的代码
每次递归都将问题的规模缩小，在题目中即缩小两个节点的长度，当缩小到没有节点或者只有一个节点时，直接返回该节点的值，因为没办法交换，返回值给上一层中两个节点的第一节点的next值。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head; //终止条件
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}
方法二：迭代法
每次交换两个节点，思考终止条件
首先设置一个哑结点dummyHead = new ListNode(0); ListNode prev, cur, next
一开始
0->1->2->3->4 ， prev = 0, cur = 1, next = 2
交换
prev.next = cur;
cur.next = next.next;
next.next = cur;
一次迭代后
0->2->1->3->4, prev = 0, cur = 1, next = 2
更新 prev, cur, next
prev = cur;
cur = next.next;
next = cur.next;
继续后面的迭代
终止条件：
- 奇数个节点（只剩一个节点未交换也不用交换）， next = null
- 偶数个节点（一个节点不剩）， cur = null
/**
* 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 dummyHead = new ListNode(0);
ListNode prev = dummyHead, cur = head;
prev.next = head;
while(cur != null){
ListNode next = cur.next;
if(next == null) break; //只剩一个节点不需要交换
prev.next = next;
cur.next = next.next;
next.next = cur;
prev = cur;
cur = cur.next;
}
return dummyHead.next;
}
}
