【牛客面试必刷TOP101】Day1.反转链表和合并两个排序的链表

作者简介：大家好，我是未央；

博客首页：未央.303

系列专栏：牛客面试必刷TOP101

每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！

文章目录

前言

一.反转链表

题目描述

解题分析

二.合并两个排序的链表

题目描述

解题分析

总结

前言

今天是我们第一天的牛客面试必刷TOP101，比较简单，一定要好好掌握清楚；每天见！！！

一.反转链表

题目描述

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤10000≤n≤1000

要求：空间复杂度O(1) ，时间复杂度 O(n) 。

举例说明：

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1：

示例2：

解题分析

解题思路:

首先本题我们决定采用栈的方法来反转链表最为简单；

因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表；

代码编写思路步骤：

1.创建一个空栈和一个辅助指针current ，并将current指向链表的头节点。

⒉将节点逐个压入栈中，直到链表的末尾。每次压入节点时，将current 指针向后移动到下一个节点。

3.弹出栈中的节点，并将其依次连接起来，形成新的链表。

在这个过程中，需要保持一个指针prev ，用来指向新链表的头节点。

4.重复步骤3直到栈为空，此时所有的节点都已经被反转。

5.将新链表的头节点返回作为结果。

复杂度分析：

时间复杂度为O(n)，其中n表示链表的长度。

空间复杂度是O(1)，因为反转链表时只需要使用几个指针变量，不需要额外的数据结构来存储节点。

图示说明:

代码编写：

详细代码解析：

步骤4中23~28行代码：
while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            prev.next = node;
            prev = node;
        }
解析：

在上述代码中，prev.next = node 的作用是将 prev 节点的 next 指针指向 node 节点，即将当前节点与前一个节点进行连接。

首先，我们将栈中弹出的第一个节点作为新链表的头节点，将其赋给 newHead 变量。

接下来，在循环中，我们使用 prev 变量来表示当前的节点，而 node 变量则表示从栈中弹出的下一个节点。于是，prev.next = node 表示将 prev 节点的 next 指针指向 node 节点，将它们连接在一起。

然后，通过 prev = node 操作，将 prev 更新为当前的节点 node，以便在下一次循环中连接下一个节点。

通过这样的操作，我们可以依次将栈中的节点连接起来，最终形成反转后的链表。在循环结束后，prev 指向的是新链表的尾节点。

二.合并两个排序的链表

题目描述

描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤10000≤n≤1000，−1000≤节点值≤1000−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)。

举例说明：

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1：

示例2：

示例3：

解题分析

解题思路：

本题我们决定采用递归的方法解决比较简单方便；

分类讨论：

1.如果有一个链表为空，返回另一个链表（特殊情况）
2.如果pHead1 节点值比小pHead2，下一个节点应该是 pHead1，应该return pHead1，在return之前，指定pHead1的下一个节点应该是pHead1.next和pHead2俩链表的合并后的头结点；
3.如果pHead1 节点值比pHead2大，下一个节点应该是pHead2，应该return pHead2，在return之前，指定pHead2的下一个节点应该是pHead1和pHead2.next俩链表的合并后的头结点；

代码编写思路步骤：

1.首先，编写一个递归函数，用于合并两个排序链表。

2.在递归函数中，判断某个链表是否为空。如果其中一个链表为空，说明已经到达链表的末尾，直接返回另一个链表。（特殊情况）

3.如果两个链表都不为空，比较两个链表的头节点的值。将较小的头节点作为合并后链表的头节点。

4.然后，递归地调用合并函数，传入较小头节点的下一个节点和另一个链表。将递归返回的结果连接到较小头节点的后面，形成合并后的链表。

5.最后，返回合并后的链表作为结果。

复杂度分析：

时间复杂度O(N+M)：M N分别表示pHead1, pHead2的长度；

空间复杂度O(1)：常数级空间；