分享一下我的第24题递归写法，顺便求解递归空间复杂度的分析？

Question

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        //linkedlist at least has two elements.
        ListNode next = head.next;
        head.next = swapPairs(head.next.next);
        next.next = head;
        return next;
    }
}

感觉第24题用递归逻辑会更简洁明了一点。顺便问一下波波老师，这种情况的递归空间复杂度是O(1)还是O(N)? 我觉得是O(1)但是不是很确定

Answer 1

liuyubobobo 2019-05-09 01:21:56

感谢分享：）

时间复杂度是O(n)的。你的链表有多长，就会调用swapPairs多少次：）

继续加油！：）

• 提问者 幕布斯1098637 #1

  老师，空间复杂度呢？

• liuyubobobo 回复 提问者 幕布斯1098637 #2

  也是O(n)。递归算法占用系统栈。