目录
大家好，今天我就来给大家分析一下我上期分享的题目的详细解析，编程的能力都是逐步提升的，但是思维的锻炼可以提前进行，这样有助于我们以后自己对着陌生的代码进行分析。废话不多说，我们现在开始。（完整代码在文章最后）
题目:
1.以单链表作为存储结构，实现线性表的就地逆置（提示，就地逆置：在不使用额外的数据结构或空间的情况下，将单链表中的节点顺序反转，使得原本指向下一个节点的指针指向了前一个节点。完成这一操作后，链表的第一个数据元素变为最后一个数据元素，而最后一个数据元素则成为第一个数据元素）。
2. 创建一个非递减序（有重复值）的单链表，实现删除值相同的多余结点。
考点分析：
基础：单链表的相关知识（单链表的存储结构，基本的用法）
重点：链表的就地逆置，非递减链表，删除相同元素。
这里的基础我们就不再赘述，由于篇幅原因我们就主要讲一讲重点。
难点1：就地逆置
使链表的元素可以在存储空间内进行顺序替换。
步骤：
- 初始化三个指针，一个指向链表的头节点（但不包括头节点，仅作为遍历的起点），一个初始化为空（用于构建新的链表头），另一个用于遍历链表。
- 遍历链表，对于每个遍历到的节点：
- 将当前节点的下一个节点保存起来，以便在遍历结束后能够继续遍历。
- 将当前节点的指针指向新的链表头（即之前为空的那个指针所指向的位置）。
- 更新新的链表头为当前节点。
- 当遍历完成后，新的链表头即为逆置后的链表的头节点。
这种方法通过迭代的方式，逐个将链表节点从原链表中“删除”并插入到新的链表中，最终实现了链表的逆置。
代码实现：
就地逆置的函数
// 就地逆置链表
void reverseList()
{
ListNode* prev = nullptr;
ListNode* current = head;
ListNode* next = nullptr;
while (current!= nullptr)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}大家看到上面的代码有没有一种熟悉的感觉。没错核心思想还是变量的交换问题。
首先我们先定义两个空指针，定义一个指针指向头节点。由于就地逆置需要将整个链表都进行操作，所以我们需要一个循环，循环条件就是我们的current指针不为空（逆置会使我们的头指针变成尾指针，所以这就是第一个关键点，循环条件的确立）。核心步骤：首先我们先将next指向current的next域；next指向current的next域赋值为prev指针；然后prev指针指向current指针指向的地址；current指针指向next指针指向的地址。最后循环外我们将头指针指向prev指针。
核心代码详细解释：
- 定义指针变量：
ListNode* prev = nullptr;：定义一个指针prev，初始化为nullptr，用于记录当前节点的前一个节点。在反转过程中，prev将指向当前已反转部分的最后一个节点。ListNode* current = head;：定义一个指针current，初始化为链表的头节点head，用于遍历链表。ListNode* next = nullptr;：定义一个指针next，初始化为nullptr，用于暂存current节点的下一个节点，因为在反转current节点的指针之前需要知道它的下一个节点是什么。- 遍历链表并反转：
while (current != nullptr)：当current不为nullptr时，继续循环。这意味着只要还没有到达链表的末尾（即current不是nullptr），就继续反转过程。- 反转当前节点的指针：
next = current->next;：首先，保存current节点的下一个节点到next。current->next = prev;：然后，将current节点的next指针指向前一个节点prev，完成当前节点的反转。- 移动指针：
prev = current;：将prev移动到当前节点，因为当前节点现在已经是反转后链表的最后一个节点。current = next;：将current移动到下一个待反转的节点（即之前保存的next）。- 更新头节点：
head = prev;：当current变为nullptr，表示已经遍历并反转了整个链表。此时，prev指向的是新链表的头节点（即原链表的尾节点），因此更新head为prev。总结：
这段代码通过三个指针prev、current和next，在不使用额外存储空间的情况下，实现了单链表的原地反转。遍历链表时，逐个节点地将它们的指针指向前一个节点，最终将链表的头节点更新为反转后的新头节点。
难点2：①非递减链表，②删除相同元素
首先就是第一个函数：非递减链表：
代码详解①：
- 创建新节点：
ListNode* newNode = new ListNode(val);：首先，创建一个新的ListNode节点，并用传入的val值初始化它的数据部分。- 处理特殊情况：
if (head == nullptr || val <= head->data)：检查链表是否为空（head == nullptr）或者新节点的值小于或等于头节点的值。如果是这两种情况之一，说明新节点应该被插入到链表的开头。
newNode->next = head;：将新节点的next指针指向当前的头节点。head = newNode;：更新头指针，使其指向新节点。- 在链表中间或末尾插入节点：
- 如果新节点的值大于头节点的值，并且链表不为空，那么需要找到新节点应该插入的位置。
ListNode* current = head;：定义一个指针current，初始化为链表的头节点，用于遍历链表。while (current->next != nullptr && current->next->data < val)：遍历链表，直到找到第一个其next节点的值大于或等于新节点值的节点。这意味着新节点应该被插入到这个节点之后。在这个循环中，current指针会移动到链表中值小于新节点值的最后一个节点。newNode->next = current->next;：将新节点的next指针指向current节点的下一个节点。current->next = newNode;：将current节点的next指针指向新节点，完成插入操作。
总结：
这个函数通过遍历链表，找到一个合适的位置来插入新节点，以保持链表的非递减顺序。如果链表为空或新节点的值小于或等于头节点的值，新节点会被插入到链表的开头。否则，新节点会被插入到链表中第一个值大于或等于它的节点之前。这样，链表在插入新节点后仍然保持非递减顺序。
// 插入节点以保持非递减序
void insertInOrder(int val)
{
ListNode* newNode = new ListNode(val);
if (head == nullptr || val <= head->data)
{
newNode->next = head;
head = newNode;
}
else
{
ListNode* current = head;
while (current->next!= nullptr && current->next->data < val)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}这是第二个函数：删除相同的多余节点；
代码详解②：
这段代码是一个用于删除单链表中值相同的多余节点的函数。它遍历链表，比较当前节点和下一个节点的值，如果它们相同，则删除下一个节点（即多余节点）。下面是代码的详细分析：
- 初始化：
ListNode* current = head;：定义一个指针current，初始化为链表的头节点head。这个指针将用于遍历链表。- 遍历链表：
while (current != nullptr && current->next != nullptr)：这个循环会持续进行，直到current指针到达链表的末尾（current == nullptr）或者current是链表的最后一个节点（current->next == nullptr）。由于我们需要比较当前节点和下一个节点的值，所以必须确保current->next不是nullptr。- 检查并删除重复节点：
if (current->data == current->next->data)：如果当前节点的值等于下一个节点的值，说明找到了一个重复节点（在这个上下文中，“重复”意味着相邻节点的值相同）。
ListNode* temp = current->next;：定义一个临时指针temp，指向要删除的重复节点（即current的下一个节点）。current->next = current->next->next;：将current的next指针跳过temp节点，直接指向temp的下一个节点。这样就从链表中移除了temp节点。delete temp;：释放temp节点所占用的内存。这是很重要的，因为C++中动态分配的内存如果不手动释放，会导致内存泄漏。- 移动到下一个节点：
else { current = current->next; }：如果当前节点的值不等于下一个节点的值，说明没有重复，那么current指针应该移动到下一个节点，继续遍历链表。
注意事项：
- 这个函数只删除了相邻的重复节点。如果链表中有非相邻的重复节点（例如，1 -> 2 -> 3 -> 1 -> 4），这些重复节点将不会被删除。
- 函数正确地处理了内存释放，避免了内存泄漏。
- 函数的时间复杂度是O(n)，其中n是链表中节点的数量，因为每个节点都被访问了一次。
- 函数的空间复杂度是O(1)，因为它只使用了有限数量的额外变量（
current和temp），不随链表长度变化。
// 删除值相同的多余节点
void removeDuplicates()
{
ListNode* current = head;
while (current!= nullptr && current->next!= nullptr)
{
if (current->data == current->next->data)
{
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
}
else
{
current = current->next;
}
}
}