24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
Tags:
Categories:

题意:

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

难度:

中等

示例:

输入：head = [1,2,3,4] 输出：[2,1,4,3]

分析:

看到这道题，我们要先搞清楚什么是两两交换，比如 1->2->3->4，交换后就是 2->1->4->3。

第一个和第二个交换，第三个和第四个交换，以此类推。

那么就可以把整个链转为子链, 通过递归处理

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        return swapAndConnect(head);
    }

    public ListNode swapAndConnect(ListNode node) {
        if (node == null || node.next == null) {
            // 如果当前节点或下一个节点为空，直接返回当前节点
            return node;
        }

        // 递归：获取后面的交换结果
        ListNode partner = node.next;
        ListNode next = swapAndConnect(partner.next);

        // 交换当前节点和下一个节点
        node.next = next;
        partner.next = node;

        // 返回交换后的新头节点
        return partner;
    }
}