24. 两两交换链表中的节点（中等）

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

思路：

这里由于正在学习递归思想，这次先以递归来做，这里的递归三部曲为

  1. 终止条件：链表中只剩一个节点或者已经没有节点了
  2. 返回值：返回已经进行处理的链表
  3. 本层递归：将本层中head，next，和已经处理完的链表部分，交换这三个节点的前两个

递归思想请看这里

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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;
        //一共三个节点:head, next, swapPairs
        //下面的任务便是交换这3个节点中的前两个节点
        ListNode node = head.next;
        head.next = swapPairs(node.next);
        node.next = head;
        //根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
        return node;

    }
}