给定一个链表，两两交换其中相邻的节点，并返回交换后的链表_给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改

题目原文
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例:给定 1->2->3->4, 你应该返回 2->1->4->3.
可以用递归或者非递归的方式来做这个题
非递归方式
思路：声明三个节点，前两个节点进行交换，最后一的声明的节点用来表示位置。while循环结束的条件是cur之后（包括cur）必须有两个及以上的非空节点。

 public static ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null){ //链表没有结点或者只有一个结点，直接返回不进行交换。
            return head;
        }
        ListNode pre=head;
        ListNode preNext=head.next;
        ListNode cur=preNext.next;
        //以上三个节点的声明。前两个节点进行交换，后一个节点用来声明下一次进行交换的第一个元素。
        pre.next=cur;
        preNext.next=pre;
        head=preNext;//新的头部;
        while(cur!=null&&cur.next!=null){//当cur和cur.next同时存在时才能交换，也就是要有2个以上
            preNext=cur.next;//交换时第二个结点元素
            cur=preNext.next;//下一次交换的第一个元素
            pre.next.next=cur;//这个用处比较奇妙，这个是为了保证链表的完整性。
            preNext.next=pre.next;//第二个元素后面链接第一个元素
            pre.next=preNext;//上一次的交换后的第二个元素链接本次第二个元素
            pre=preNext.next;//交换后的第二个元素
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

循环体里最终要的就是表示三个声明节点的位置，其中pre.next.next=cur，是为了保证链表的完整性。因为preNext.next=pre.next。
递归方式
思路：
刚开始链表由1->2->3->4构成。
下面的递归则是 swapPairs(1)函数开始：1->swapPairs(3) 3->swapPairs(5) //这个5指的是4的下一个节点，也就是null。
swapPairs(5)返回null，所以3->null，然后继续swapPairs（3）的后半部分，4->3->null.，并且返回4。
由于swapPairs(3)返回4，所以1->4-3-null，然后继续swapPairs（1）的后半部分，2->1->4->3->null。递归完成。

public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode first = head;
        ListNode last = head.next;
        //以上保存现场
        first.next = swapPairs(last.next);
        // 恢复现场
        last.next = first;
        return last;
    }
1
2
3
4
5
6
7
8
9
10
11
12

递归思想很大程度上依赖于栈，每次将现场压入栈中，等到最后一个返回值出现以后不断的从栈中取出，并回复现场继续执行。