[LeetCode题解]24. 两两交换链表中的节点 | 递归

方法一：递归

解题思路

递归法，假设后续链表已经完成交换，此时只需要对前两个节点进行交换，然后再连接上后续已交换的链表即可。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next.next;

        ListNode first = head, second = head.next;
        second.next = first;
        first.next = SwapPairs(next);
        
        return second;
    }
}

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 是链表的长度。一共调用 \(n/2\) 次，交换所用时间复杂度为 \(O(1)\)，因此总的时间复杂度为 \(O(n)\)。
• 空间复杂度：\(O(n)\)，其中 \(n\) 是链表的长度。一共调用 \(n/2\) 次，因此需要额外的 \(O(n)\)空间作为调用栈。