LeetCode 21-25 题详解 Java版 ( 万字图文详解 LeetCode 算法题21-25 =====＞＞＞＜建议收藏＞)

小咪咪 2022-09-16 00:15 138阅读 0赞

### 目录 ###

*  第21题. Merge Two Sorted Lists
 *  解法一 迭代
 *  解法二 递归
 *  总
 *  第22题 . Generate Parentheses
 *   *  1. 题目描述（中等难度）
 *  解法一 暴力破解
 *  解法二
 *  解法三
 *  扩展 卡塔兰数
 *  总
 *  第23题: Merge k Sorted Lists
 *  解法一 暴力破解
 *  解法二 一列一列比较
 *  解法三 优先队列
 *  解法四 两两合并
 *  解法五 两两合并优化
 *  总
 *  第24题: Swap Nodes in Pairs
 *  解法一 迭代
 *  解法二 递归
 *  总
 *  第25题 : Reverse Nodes in k-Group
 *  解法一 迭代
 *  解法二递归
 *  总
 *  喜欢 请点个 + 关注

# 第21题. Merge Two Sorted Lists #

题目描述（简单难度）

![img][]

合并两个有序链表。

# 解法一 迭代 #

遍历两个链表。

时间复杂度：O（m + n）。

空间复杂度：O（1）。

# 解法二 递归 #

参考\[这里\](https://leetcode.wang/Merge Two Sorted Lists)

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if(l1 == null) return l2;
        if(l2 == null) return l1;
    
        if(l1.val < l2.val) {
        
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
        
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
    }

时间复杂度：

空间复杂度：

# 总 #

递归看起来，两个字，优雅！但是关于递归的时间复杂度，空间复杂度的求法，先留个坑吧。

# 第22题 . Generate Parentheses #

## 1. 题目描述（中等难度） ##

![img][img 1]

给一个数字 n ，返回所有合法的括号匹配，刚好和\[20题\](https://leetcode.wang/leetCode-20-Valid Parentheses.html)相反。

自己没想出来，全部参考 LeetCode 给出的 [Solution][]。

# 解法一 暴力破解 #

列举所有的情况，每一位有左括号和右括号两种情况，总共 2n 位，所以总共 22n2^\{2n\}22n 种情况。

public List<String> generateParenthesis(int n) {
        
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    
    public void generateAll(char[] current, int pos, List<String> result) {
        
        if (pos == current.length) {
        
            if (valid(current))
                result.add(new String(current));
        } else {
        
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }
    
    public boolean valid(char[] current) {
        
        int balance = 0;
        for (char c: current) {
        
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }

时间复杂度：对每种情况判断是否合法需要 O（n），所以时间复杂度是 O(22nn)O(2^\{2n\}n)O(22nn) 。

空间复杂度：O(22nn)O(2^\{2n\}n)O(22nn)，乘以 n 是因为每个串的长度是 2n。此外这是假设所有情况都符合的时候，但其实不可能都符合，后边会给出更精确的情况。

# 解法二 #

解法一中，我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。

还有一种情况就是如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。因为每个右括号必须和之前的某个左括号匹配，如果右括号数量多于左括号，那么一定有一个右括号没有与之匹配的左括号，后边不论加多少左括号都没有用了。例如 n = 3 ，总共会有 6 个括号，我们加到 ( ) ) 3 个括号的情况的时候，有 1 个左括号，2 个右括号，此时后边 3 个括号无论是什么，已经注定它不会是合法序列了。

基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。

public List<String> generateParenthesis(int n) {
        
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }
    
    public void backtrack(List<String> ans, String cur, int left, int right, int n){
        
        if (cur.length() == n * 2) {
        
            ans.add(cur);
            return;
        }
        //左括号不要超过 n
        if (left < n)
            backtrack(ans, cur+"(", left+1, right, n);
        //右括号不要超过左括号
        if (right < left)
            backtrack(ans, cur+")", left, right+1, n);
    }

时间复杂度：

空间复杂度：

递归的复杂度分析，继续留坑 =.=。

# 解法三 #

解法二中是用列举的方法，仔细想想，我们每次用递归的时候，都是把大问题换成小问题然后去解决，这道题有没有这个思路呢？

我们想一下之前的列举过程，第 0 个位置一定会是左括号，然后接着添加左括号或右括号，过程中左括号数一定大于或等于右括号数，当第一次出现左括号数等于右括号数的时候，假如此时的位置是 c 。那么位置 1 到 c - 1 之间一定是合法序列，此外 c + 1 到最后的 2n -1 也是合法序列。而假设总共是 n 组括号，1 到 c - 1 是 a 组括号， c + 1 到 2n - 1 之间则是 n - 1 - a 组括号，如下图

![img][img 2]

最重要的是，每一个合法序列都会有这么一个数 c ，且唯一。所以我们如果要求 n 组括号的所有序列，只需要知道 a 组括号以及 ( n - a - 1) 组括号的所有序列，然后两两组合即可。

以 n = 3 为例，我们把 0 到 c 之间的括号数记为 a 组， c + 1 到最后的括号数记为 b 组，则

a = 0，b = 2 对应 （）（（））以及 （）（）（） 两种情况，此时 c = 1。

![img][img 3]

![img][img 4]

a = 1，b = 1，对应 （（））（（）） 一种情况，此时 c = 3。

![img][img 5]

a = 2，b = 0 对应 （（（）））， （（）（）） 两种情况，此时 c = 5。

![img][img 6]

![img][img 7]

所以我们如果要想求 n 组括号，只需要知道 a 组和 b 组的情况，然后组合起来就可以了。

看起来我们在迭代 a ，其实本质上是在迭代 c ，c = 2a + 1，迭代 a 从 0 到 n - 1 ，就是迭代 c 从 1 到 2n - 1。看起来 c 都是奇数，其实是可以理解的，因为 0 到 c 间都是一组组的括号， 所以 c 一定是奇数。为什么可以迭代 c ，因为上边说到每一个合法序列都对应着一个 c ，遍历 c 的话，就能得到所有的情况了，看一下代码吧。

public List<String> generateParenthesis(int n) {
        
        List<String> ans = new ArrayList();
        if (n == 0) {
        
            ans.add("");
        } else {
        
            for (int a = 0; a < n; a++)
                for (String left: generateParenthesis(a))
                    for (String right: generateParenthesis(n-1-a))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }

时间复杂度：

空间复杂度：

留坑。

# 扩展 卡塔兰数 #

如果这道题不是让你列举所有的情况， 而是仅仅让你输出 n 对应下有多少种合法序列，该怎么做呢？

答案就是 1n+1C2nn\\frac\{1\}\{n+1\}C^n\_\{2n\}n+11C2nn，也可以写成1n+1(2nn)\\frac\{1\}\{n+1\}\\binom\{2n\}\{n\}n+11(n2n)。怎么证明呢？我主要参考了[这里][Link 1]，说一下。

我们假设不考虑是不是合法序列，那么就一共有C2nnC^n\_\{2n\}C2nn种情况，然后我们只需要把里边的非法情况减去就可以了，一共有多少种非法情况呢？

首先我们用C2nnC^n\_\{2n\}C2nn就保证了一定是有 n 个左括号，n 个右括号，那么为什么出现了非法序列？

为了方便论述，我们把左括号记为 +1，右括号记为 -1.

ps：下边的 和 都是指两个数的和，不是你和我中的和。

我们假设非法序列的**集合是 M** ，而非法序列就是列举过程中右括号数比左括号数多了，也就是和小于 0 了，变成 -1 了。这种情况一旦出现，后边无论是什么括号都改变不了它是非法序列的命了。我们将第一次和等于 -1 的时候的位置记为 d 。每一个非法序列一定存在这样一个 d 。然后关键的地方到了！

此时我们把 0 到 d 所有的 -1 变成 1，1 变成 -1，我们将每一个非法序列都这样做，就构成了一个**新的集合 N** ，并且这个集合 N 一定和 M 中的元素一一对应（ N -> M，在集合 N 中第一次出现和为 1 的位置也就是 d ，把 0 到 d 中所有的 -1 变成 1，1 变成 -1 就回到了 M），从而集合 M 的数量就等于集合 N 的数量。集合 N 的数量是多少呢？

我们来分析下集合 N 是什么样的，集合 N 对应的集合 M 原来的序列本来是这样的，在 0 到 d 之间和是 -1 ，也就是 -1 比 +1 多一个，d + 1 到最后的和一定是 1（因为 n 个 +1 和 n 个 -1 的和一定是 0 ，由于 0 到 d 和是 -1，后边的和一定是 1），也就意味着 +1 比 -1 多一个。而在集合 N 中，我们把 0 到 d 的 -1 变成了 +1 ，+1 变成了 -1 ，所以也变成了 +1 比 -1 多一个，所以集合 N 总共就是 +1 比 -1 多 2 个的集合，也就是 n + 1 个 +1 和 n - 1 个 -1 。

所以集合 N 就是 2n 个位置中选 n - 1 个位置放 -1，其他位置放 +1，总共就有 C2nn−1C^\{n - 1\}*\{2n\}C2nn−1，所以集合 M 也有 C2nn−1C^\{n - 1\}*\{2n\}C2nn−1种。

所有合法序列就有 C2nn−C2nn−1=1n+1C2nnCn\_\{2n\}-C\{n-1\}*\{2n\}=\\frac\{1\}\{n+1\}C^n*\{2n\}C2nn−C2nn−1=n+11C2nn 。

将集合 M 和集合 N 建立了一一映射，从而解决了问题，神奇！！！！！！！！！！其实，这个数列就是卡塔兰数，可以看下[维基百科][Link 2]的定义。

![img][img 8]

而这个数列，其实除了括号匹配，还有很多类似的问题，其本质是一样的，例如，

2n 个人排队买票，其中 n 个人持 50 元，n 个人持 100 元。每张票 50 元，且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序，不至于使售票处找不开钱？

对于一个无限大的栈，一共n个元素，请问有几种合法的入栈出栈形式？

P = a1 *a2* a3 *…* an，其中 ai 是矩阵。根据乘法结合律，不改变矩阵的相互顺序，只用括号表示成对的乘积，试问一共有几种括号化方案？

n 个结点可构造多少个不同的二叉树？

… …

更多例子可以看[维基百科][Link 2]和[这里][Link 3]。

而 Solutin 给出的时间复杂度，其实就是卡特兰数。

![img][img 9]

[维基百科][Link 2]的给出的性质。

![img][img 10]

# 总 #

本以为这道题挺常规的，然后自己一直卡在解法三的理解上，查来查去，竟然查出了卡塔兰数，虽然似乎和解法三也没什么关系，但又开阔了很多思路。解法三分析出来的迭代方法，以及用映射证明卡塔兰数的求法，棒！

# 第23题: Merge k Sorted Lists #

1.  题目描述（困难难度）

![img][img 11]

k 个有序链表的合并。

我们用 N 表示链表的总长度，考虑最坏情况，k 个链表的长度相等，都为 n 。

# 解法一 暴力破解 #

简单粗暴，遍历所有的链表，将数字存到一个数组里，然后用快速排序，最后再将排序好的数组存到一个链表里。

public ListNode mergeKLists(ListNode[] lists) {
        
        List<Integer> l = new ArrayList<Integer>();
        //存到数组
        for (ListNode ln : lists) {
        
            while (ln != null) {
        
                l.add(ln.val);
                ln = ln.next;
            }
        }
        //数组排序
        Collections.sort(l);
        //存到链表
        ListNode head = new ListNode(0);
        ListNode h = head;
        for (int i : l) {
        
            ListNode t = new ListNode(i);
            h.next = t;
            h = h.next;
        }
        h.next = null;
        return head.next;
    }

时间复杂度：假设 N 是所有的数字个数，存到数组是 O（N），排序如果是用快速排序就是 O(NlogN)O(Nlog\_N)O(NlogN) ，存到链表是 O（N），所以取个最大的，就是 O(NlogN)O(Nlog\_N)O(NlogN)。

空间复杂度：新建了一个链表，O（N）。

# 解法二 一列一列比较 #

![img][img 12]

我们可以一列一列的比较，将最小的一个存到一个新的链表里。

public ListNode mergeKLists(ListNode[] lists) {
        
        int min_index = 0;
        ListNode head = new ListNode(0);
        ListNode h = head;
        while (true) {
        
            boolean isBreak = true;//标记是否遍历完所有链表
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < lists.length; i++) {
        
                if (lists[i] != null) {
        
                    //找出最小下标
                    if (lists[i].val < min) {
        
                        min_index = i;
                        min = lists[i].val;
                    }
                    //存在一个链表不为空，标记改完 false
                    isBreak = false;
                }
    
            }
            if (isBreak) {
        
                break;
            }
            //加到新链表中
            ListNode a = new ListNode(lists[min_index].val);
            h.next = a;
            h = h.next;
            //链表后移一个元素
            lists[min_index] = lists[min_index].next;
        }
        h.next = null;
        return head.next;
    }

时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。

空间复杂度：N 表示最终链表的长度，则为 O（N）。

其实我们不需要创建一个新链表保存，我们只需要改变得到的最小结点的指向就可以了。

public ListNode mergeKLists(ListNode[] lists) {
        
        int min_index = 0;
        ListNode head = new ListNode(0);
        ListNode h = head;
        while (true) {
        
            boolean isBreak = true;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < lists.length; i++) {
        
                if (lists[i] != null) {
        
                    if (lists[i].val < min) {
        
                        min_index = i;
                        min = lists[i].val;
                    }
                    isBreak = false;
                }
    
            }
            if (isBreak) {
        
                break;
            }
            //最小的节点接过来
            h.next = lists[min_index];
            h = h.next;
            lists[min_index] = lists[min_index].next;
        }
        h.next = null;
        return head.next;
    }

时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。

空间复杂度：O（1）。

# 解法三 优先队列 #

解法二中，我们每次都是取出一个最小的，然后加入一个新的， O（1）的复杂度，再找最小的，O（k） 的复杂度。我们完全可以用一个优先队列。

![img][img 13]

我们将优先级定义为数越小优先级越高，如果用堆实现优先队列，这样我们每次找最小不再需要 O（k），而是 O（log（k）），当然这样的话，我们加入新的话不再是 O（1），也需要 O（log（k））。可以看看[这里][Link 4]和[这里][Link 5]。

public ListNode mergeKLists(ListNode[] lists) {
        
            //定义优先队列的比较器
            Comparator<ListNode> cmp;
            cmp = new Comparator<ListNode>() {
          
            @Override
            public int compare(ListNode o1, ListNode o2) {
        
                // TODO Auto-generated method stub
                return o1.val-o2.val;
            }
            };
    
            //建立队列
            Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
            for(ListNode l : lists){
        
                if(l!=null){
        
                    q.add(l);
                }        
            }
            ListNode head = new ListNode(0);
            ListNode point = head;
            while(!q.isEmpty()){
        
                //出队列
                point.next = q.poll();
                point = point.next;
                //判断当前链表是否为空，不为空就将新元素入队
                ListNode next = point.next;
                if(next!=null){
        
                    q.add(next);
                }
            }
            return head.next;
        }

时间复杂度：假如总共有 N 个节点，每个节点入队出队都需要 log（k），所有时间复杂度是 O（N log（k））。

空间复杂度：优先队列需要 O（k）的复杂度。

# 解法四 两两合并 #

利用[之前][Link 6]合并两个链表的算法，我们直接两两合并，第 0 个和第 1 个链表合并，新生成的再和第 2 个链表合并，新生成的再和第 3 个链表合并…直到全部合并完。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode h = new ListNode(0);
        ListNode ans=h;
        while (l1 != null && l2 != null) {
        
            if (l1.val < l2.val) {
        
                h.next = l1;
                h = h.next;
                l1 = l1.next;
            } else {
        
                h.next = l2;
                h = h.next;
                l2 = l2.next;
            }
        }
        if(l1==null){
        
            h.next=l2;
        }
        if(l2==null){
        
            h.next=l1;
        } 
        return ans.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        
        if(lists.length==1){
        
            return lists[0];
        }
        if(lists.length==0){
        
            return null;
        }
        ListNode head = mergeTwoLists(lists[0],lists[1]);
        for (int i = 2; i < lists.length; i++) {
        
            head = mergeTwoLists(head,lists[i]);
        }
        return head;
    }

时间复杂度：不妨假设是 k 个链表并且长度相同，链表总长度为 N，那么第一次合并就是 N/k 和 N/k ，第二次合并就是 2 \* N/k 和 N/k，第三次合并就是 3 \* N/k 和 N / k，总共进行 n - 1 次合并，每次合并的时间复杂度是 O（n），所以总时间复杂度就是O(∑i=1k−1(i∗Nk+Nk))=O(kN)O(\\sum\_\{i=1\}^\{k-1\}(i\*\\frac\{N\}\{k\}+\\frac\{N\}\{k\}))=O(kN)O(∑i=1k−1(i∗kN+kN))=O(kN)，可以将两项分开，N/k 其实是常数，分开的第一项是等差数列。

空间复杂度：O（1）。

# 解法五 两两合并优化 #

依旧假设是 k 个链表，合并的过程优化下，使得只需要合并 log（k）次。

![img][img 14]

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode h = new ListNode(0);
        ListNode ans=h;
        while (l1 != null && l2 != null) {
        
            if (l1.val < l2.val) {
        
                h.next = l1;
                h = h.next;
                l1 = l1.next;
            } else {
        
                h.next = l2;
                h = h.next;
                l2 = l2.next;
            }
        }
        if(l1==null){
        
            h.next=l2;
        }
        if(l2==null){
        
            h.next=l1;
        } 
        return ans.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        
        if(lists.length==0){
        
            return null;
        }
        int interval = 1;
        while(interval<lists.length){
        
            System.out.println(lists.length);
            for (int i = 0; i + interval< lists.length; i=i+interval*2) {
        
                lists[i]=mergeTwoLists(lists[i],lists[i+interval]);            
            }
            interval*=2;
        }
    
        return lists[0];
    }

时间复杂度：假设每个链表的长度都是 `n` ，有 `k` 个链表，记总结点数是 `N = n * k`，那么时间复杂度就是O(∑i=1log2kN)=O(Nlogk)O(\\sum\_\{i=1\}^\{log\_2k\}N)=O(Nlogk)O(∑i=1log2kN)=O(Nlogk)。

空间复杂度：O（1）。

# 总 #

优先队列的运用印象深刻，此外对两两链表的合并，我们仅仅改变了合并的方式就将时间复杂度降低了很多，美妙！

# 第24题: Swap Nodes in Pairs #

题目描述（中等难度）

![img][img 15]

给定一个链表，然后两两交换链表的位置。

# 解法一 迭代 #

首先为了避免单独讨论头结点的情况，一般先申请一个空结点指向头结点，然后再用一个指针来遍历整个链表。

先来看一下图示：

![img][img 16]

![img][img 17]

![img][img 18]

![img][img 19]

![img][img 20]

point 是两个要交换结点前边的一个位置。

public ListNode swapPairs(ListNode head) {
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode point = dummy;
        while (point.next != null && point.next.next != null) {
         
            ListNode swap1 = point.next;
            ListNode swap2 = point.next.next;
            point.next = swap2;
            swap1.next = swap2.next;
            swap2.next = swap1;
            point = swap1;
        }
        return dummy.next;
    }

时间复杂度：O（n）。

空间复杂度：O（1）。

# 解法二 递归 #

参考[这里][Link 7]。

自己画了个参考图。

![img][img 21]

![img][img 22]

public ListNode swapPairs(ListNode head) {
        
        if ((head == null)||(head.next == null))
            return head;
        ListNode n = head.next;
        head.next = swapPairs(head.next.next);
        n.next = head;
        return n;
    }

递归时间复杂度留坑。

# 总 #

自己开始没有想出递归的算法，每次都会被递归的简洁吸引。另外，感觉链表的一些题，只要画图打打草稿，搞清指向关系，一般不难。

# 第25题 : Reverse Nodes in k-Group #

题目描述（困难难度）

![img][img 23]

将一个链表，每 k 个倒置，最后一组不足 k 个就不倒置。

# 解法一 迭代 #

关于单链表倒置，我们在[第 2 题][2]就讨论过。有了单链表倒置，这道题无非就是用一个循环，每次将 k 个结点取下来，倒置后再接回去，然后再取 k 个，以此循环，到了最后一组如果不足 k 个，不做处理，直接返回头结点就可以了。所以关键就是，指针指来指去，大家不晕掉就好，我做了图示，大家参考一下。

为了将头结点也一般化，我们创建一个 dummy 结点，然后整个过程主要运用三个指针， tail 指针表示已经倒置后的链表的尾部，subhead 指针表示要进行倒置的子链表，toNull 指针为了将子链表从原来链表中取下来。

![img][img 24]

一个 while 循环，让 toNull 指针走 k - 1 步使其指向子链表的尾部。中间的 if 语句就是判断当前节点数够不够 k 个了，不够的话直接返回结果就可以了。

![img][img 25]

将子链表指向 null ，脱离出来。并且用 temp 保存下一个结点的位置。

![img][img 26]

然后调用倒置函数，将子链表倒置。

![img][img 27]

接下来四步分别是，新链表接到 tail（注意下边的图 tail 是更新后的位置，之前 tail 在 dummy 的位置） 的后边；更新 tail 到新链表的尾部，也就是之前的 subhead （下图 subhead 也是更新后的位置，之前的位置参见上边的图）；sub\_head 更新到 temp 的位置；toNull 到 sub\_head 的位置；然后将新的尾部 tail 把之前断开的链表连起来，接到 sub\_head 上。

![img][img 28]

整理下其实就是下边的样子

![img][img 29]

和初始的时候（下边的图）对比一下，发现 tail，subhead 和 toNull 三个指针已经就位，可以愉快的重复上边的步骤了。

![img][img 24]

看下代码吧。

public ListNode reverseKGroup(ListNode head, int k) {
        
        if (head == null)
            return null;
        ListNode sub_head = head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;
        ListNode toNull = head;
        while (sub_head != null) {
        
            int i = k;
            //找到子链表的尾部
            while (i - 1 > 0) {
        
                toNull = toNull.next;
                if (toNull == null) {
        
                    return dummy.next;
                }
                i--;
            }
            ListNode temp = toNull.next;
            //将子链表断开
            toNull.next = null;
            ListNode new_sub_head = reverse(sub_head); 
            //将倒置后的链表接到 tail 后边
            tail.next = new_sub_head;
            //更新 tail 
            tail = sub_head; //sub_head 由于倒置其实是新链表的尾部
            sub_head = temp;
            toNull = sub_head;
            //将后边断开的链表接回来
            tail.next = sub_head;
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode head) {
        
        ListNode current_head = null;
        while (head != null) {
        
            ListNode next = head.next;
            head.next = current_head;
            current_head = head;
            head = next;
        }
        return current_head;
    }

时间复杂度：while 循环中本质上我们只是将每个结点访问了一次，加上结点倒置访问的一次，所以总共加起来每个结点其实只访问了 2 次。所以时间复杂度是 O（n）。

空间复杂度：O（1）。

# 解法二递归 #

有没有被解法一的各种指针绕晕呢，我们有一个更好的选择，递归，这样看起来就会简洁很多。

public ListNode reverseKGroup(ListNode head, int k) {
        
        if (head == null)
            return null;
        ListNode point = head;
        //找到子链表的尾部
        int i = k;
        while(i - 1 >0){
        
            point = point.next;
            if (point == null) {
        
                return head;
            }
            i--;
        }
        ListNode temp = point.next;
         //将子链表断开
        point.next = null;
    
        //倒置子链表，并接受新的头结点
        ListNode new_head = reverse(head);
    
        //head 其实是倒置链表的尾部，然后我们将后边的倒置结果接过来就可以了
        //temp 是链表断开后的头指针，可以参考解法一的图示
        head.next = reverseKGroup(temp,k);
        return new_head;
    }
    public ListNode reverse(ListNode head) {
        
        ListNode current_head = null;
        while (head != null) {
        
            ListNode next = head.next;
            head.next = current_head;
            current_head = head;
            head = next;
        }
        return current_head;
    }

复杂度：递归留坑。

# 总 #

还是那句话，涉及到链表的，我们就画下图，把各个指针的移动理清楚，一般没啥问题。

今天我们一起学习了LeetCode 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!

# 喜欢 请点个 + 关注 #

[img]: /images/20220828/dd8ff8458a2e475ba7d9c2307420a0e7.png
[img 1]: /images/20220828/c9a967aada894010b164826e6f6c384f.png
[Solution]: https://leetcode.com/problems/generate-parentheses/solution/
[img 2]: /images/20220828/d6cc7d692a8a49dabc582427eb472d29.png
[img 3]: /images/20220828/30de69d0e52b43e2897cc9842b1d3a05.png
[img 4]: /images/20220828/912f4680a6054934a6c91266e4d0014d.png
[img 5]: /images/20220828/5c3173f8f5f74652b20e483ca6faf870.png
[img 6]: /images/20220828/1413294fc8c34a8099616966833772d4.png
[img 7]: /images/20220828/69a11b326c9847c391906f138b44f1cd.png
[Link 1]: http://lanqi.org/interests/10939/
[Link 2]: https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
[img 8]: /images/20220828/ec95921b4ae84b60aa8d3e621121cd08.png
[Link 3]: http://www.cnblogs.com/wuyuegb2312/p/3016878.html
[img 9]: /images/20220828/75218e4cc97a4149a07e3087b3269975.png
[img 10]: /images/20220828/26f81499c2da4119865c52bee7ec28e6.png
[img 11]: /images/20220828/4528334d92764e24945007ff24d28b82.png
[img 12]: /images/20220828/b8fb157fc96545bd845e9559d961d43a.png
[img 13]: /images/20220828/ef6f8c83511541a58832ab20ef68690e.png
[Link 4]: http://blog.51cto.com/ahalei/1425314?source=dra
[Link 5]: http://blog.51cto.com/ahalei/1427156
[Link 6]: https://leetcode.windliang.cc/leetCode-21-Merge-Two-Sorted-Lists.html
[img 14]: /images/20220828/4f0a36b7b5284251ac680e7cc7a1342c.png
[img 15]: /images/20220828/0da45f981c34459c9edc3e115dbbce13.png
[img 16]: /images/20220828/cc5007251c5f43debb0c3737c25ec43f.png
[img 17]: /images/20220828/0ddc2cb761104c1289dd14dc0a9ff18e.png
[img 18]: /images/20220828/a1227cca10e34883bef0e5ff728be8c0.png
[img 19]: /images/20220828/953e2a71e9174a4187ae7d6b19511c02.png
[img 20]: /images/20220828/859b45bf272e415b80db6a652fd66a8e.png
[Link 7]: https://leetcode.com/problems/swap-nodes-in-pairs/discuss/11030/My-accepted-java-code.-used-recursion.
[img 21]: /images/20220828/a8ea133a219f4b25ab5447802a4a1a2e.png
[img 22]: /images/20220828/17c661acf21d4f618b6806773cf51f3c.png
[img 23]: /images/20220828/74911bc1481e4f6baa6d35002dfe1c0a.png
[2]: https://leetcode.windliang.cc/leetCode-2-Add-Two-Numbers.html
[img 24]: /images/20220828/04d4b293f356431cad86205ecf2821f4.png
[img 25]: /images/20220828/c7ea7d0ec57a405996b8388a6c9ede30.png
[img 26]: /images/20220828/923a35d5fbe4457e91549bb3f32e334e.png
[img 27]: /images/20220828/b1f0d8c7faca4851b1d82dee9cbad819.png
[img 28]: /images/20220828/92ba8595cabb41e0b5b41b5482bf3764.png
[img 29]: /images/20220828/efffb2ddd93645cab1d97ca357b2aaf5.png