LeetCode No.24 两两交换链表中的节点
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4,
返回 2->1->4->3.
Related Topics
链表
分析
由于是两两交换，因此可以采用递归，即每次交换最后两个节点
判断当前链表是否为空或者仅有一个节点，是则返回如果不是，判断是否当前节点为倒数第二个节点。 是，交换两个节点，返回交换完成的两个节点的前一个结点引用否，递归调用swapPairs, 传入head.next.next,也就是当前节点后第二个节点，交换当前节点后的第二个第三个节点，执行第1第2步。图示
代码
class Solution { public ListNode swapPairs(ListNode head) { //链表为空，直接返回 if (head == null) return head; //链表为奇数个，最后一个节点直接返回 if ( head.next == null) return head; //处理最后两个节点 if (head.next.next == null){ //三个指针，pre指向head前一位 //slow，fast慢快指针指向head和head.next ListNode fast, slow; ListNode pre = new ListNode(-1); pre.next = head; slow = head; fast = slow.next; //断开连接，交换两个节点 //slow交换后为末尾节点，next域设为null slow.next = null; fast.next = slow; pre.next = fast; //此时head不再是头节点，因为前面断开了 //节点为交换的两个节点中的后一个，而pre.next指向他 //所以返回pre.next return pre.next; } //递归 else { head.next.next = swapPairs(head.next.next); //三个指针，pre指向head前一位 //slow，fast慢快指针指向head和head.next ListNode pre = new ListNode(-1); ListNode fast, solw; solw = head; fast = head.next; pre.next = head; //断开连接，交换两个节点 //此时慢指针slow应该指向后一个节点，也就是原来的快指针fast.next pre.next = fast; solw.next = fast.next; fast.next = solw; //此时head不再是头节点，因为前面断开了 //节点为交换的两个节点中的后一个，而pre.next指向他 //所以返回pre.next return pre.next; } } }