链表递归

难度中等

题目描述

解题思路

思路一

非递归

思路二

递归
老师和同学玩游戏，同学们站成一排，依次是小明，小红，小王等等等。。。。。
老师把玩法告诉小明，于是聪明的小明决定和小红互换位置，然后把玩法告诉小王，然后小王又和小明做一样的事。。。。。。

作者：acnesu
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/zhe-di-gui-wo-kan-sha-liao-by-acnesu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

public ListNode swapPairsI(ListNode head) {
    ListNode pre = new ListNode(0);
    pre.next = head;
    ListNode temp = pre;
    while (temp.next != null && temp.next.next != null) {
        ListNode start = temp.next;
        ListNode end = temp.next.next;
        temp.next = end;
        start.next = end.next;
        end.next = start;
        temp = start;
    }
    return pre.next;
}
public ListNode swapPairsII(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    // next 后面就不管了，直接递归。。。。
    next.next = swapPairsII(next.next);
    //下面两行代码是交换链表两个节点
    head.next = next.next;
    next.next = head;
    // 交换后，next 就是前面的节点
    return next;
}