【算法与数据结构】【链表篇】【题1-题5】

ops/2024/11/8 12:44:18/

题1.从尾到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。链表的定义如下：

struct ListNode
{int mValue;ListNode *mNext;ListNode *mPrev;
};

1.1 方法一：栈

思路：要反过来打印，首先需要遍历，那么从先遍历的节点后打印，典型的后进先出，符合栈的结构。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;struct ListNode
{int mValue;ListNode *mNext;
};void reverselist(ListNode *pHead)
{if (pHead == nullptr){return;}stack<ListNode *> reversenodes; // 创建一个栈容器ListNode *node = pHead;while (node != nullptr) // 遍历链表{reversenodes.push(node); // 将其放入栈容器中node = node->mNext;}while (!reversenodes.empty()) // 循环从栈取出节点{node = reversenodes.top();cout << node->mValue << endl;reversenodes.pop();}
}// 添加到链表的尾部
struct ListNode *AddToTail(ListNode *pHead, int value)
{ListNode *pNew = new ListNode(); // 创建了一个子节点pNew->mValue = value;pNew->mNext = nullptr; // 因为是向尾部节点插入值，所以其下一个节点一定是空if (pHead == nullptr) // 如果头结点为空，则当前节点为头结点{pHead = pNew;}else // 如果头结点不为空{ListNode *pnode = pHead; // 则先取出链表的头结点while (pnode->mNext != nullptr) // 如果当前节点有子节点，则说明不是最后一个节点{pnode = pnode->mNext;}pnode->mNext = pNew; // 找到了最后的节点，将此时要添加的节点放到链表的尾部}return pHead;
}int main()
{ListNode *Head = nullptr;Head = AddToTail(Head, 1);Head = AddToTail(Head, 2);Head = AddToTail(Head, 3);reverselist(Head);return 0;
}

1.2 方法二：递归

思想：递归从本质上将就是一个栈的结构，后进先出，所以我们可以当输出一个节点时候，先输入其下一个节点，然后再输出当前节点。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;struct ListNode
{int mValue;ListNode *mNext;
};void recursionlist(ListNode *pHead)
{if(pHead == nullptr)//注意递归的返回条件{return;}if(pHead->mNext != nullptr)//如果当前节点还有子节点，则递归先打印子节点的值{recursionlist(pHead->mNext);}cout<<pHead->mValue<<endl;
}// 添加到链表的尾部
struct ListNode *AddToTail(ListNode *pHead, int value)
{ListNode *pNew = new ListNode(); // 创建了一个子节点pNew->mValue = value;pNew->mNext = nullptr; // 因为是向尾部节点插入值，所以其下一个节点一定是空if (pHead == nullptr) // 如果头结点为空，则当前节点为头结点{pHead = pNew;}else // 如果头结点不为空{ListNode *pnode = pHead; // 则先取出链表的头结点while (pnode->mNext != nullptr) // 如果当前节点有子节点，则说明不是最后一个节点{pnode = pnode->mNext;}pnode->mNext = pNew; // 找到了最后的节点，将此时要添加的节点放到链表的尾部}return pHead;
}int main()
{ListNode *Head = nullptr;Head = AddToTail(Head, 2);Head = AddToTail(Head, 3);Head = AddToTail(Head, 4);recursionlist(Head);return 0;
}

题2：两数相加

题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

 难度：中等

思路：

我们知道其数字为逆序，那么两个链表的相同位置可以直接相加，如果相同位置相加值大于10，则代表要在下一位相加的时候，加1进位。

需要注意的点是：当两个链表都遍历完成，但是进位标志仍然为1，代表我们需要再创建一个节点用于进位。例如：链表1为999，链表二为1，两个相加，当访问完链表1的第三个位置时，循环退出，此时我们的结果为000并且进位标志不为0，因此我们要再创建一个节点存储1的结果，然后将其输出变为0001

代码一

struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){if (l1 == nullptr) // 如果第一个链表为空，则返回第二个链表{return l2;}if (l2 == nullptr) // 如果第二个链表为空，则返回第一个链表{return l1;}ListNode *returnlistPhead = nullptr; // 先创建返回链表的头节点链表ListNode *returnlistptail = nullptr; // 先创建返回链表的头节点链表int carry = 0; // 代表进位while (l1 != nullptr || l2 != nullptr){ListNode *node = new ListNode();if (l1 != nullptr && l2 != nullptr){if (carry + l1->val + l2->val < 10) // 如果两位相加不超过10,则不需要进位{node->val = carry + l1->val + l2->val;carry = 0; // 重置进位，代表当前位数不需要进位}else{node->val = carry + l1->val + l2->val - 10; // 如果两位相加超过10,则需要进位carry = 1;                                  // 代表当前位数需要进位}l1 = l1->next;l2 = l2->next;}else if (l1 == nullptr) // 此时l2不为空{if (carry + l2->val < 10) // 如果两位相加不超过10,则不需要进位{node->val = carry + l2->val;carry = 0; // 重置进位，代表当前位数不需要进位}else{node->val = carry + l2->val - 10; // 如果两位相加超过10,则需要进位carry = 1;                        // 代表当前位数需要进位}l2 = l2->next;}else if (l2 == nullptr) // 此时l1不为空{if (carry + l1->val < 10) // 如果两位相加不超过10,则不需要进位{node->val = carry + l1->val;carry = 0; // 重置进位，代表当前位数不需要进位}else{node->val = carry + l1->val - 10; // 如果两位相加超过10,则需要进位carry = 1;                        // 代表当前位数需要进位}l1 = l1->next;}// 插入链表中if (returnlistPhead == nullptr) // 如果返回的链表第一个元素为空{returnlistPhead = returnlistptail = node;returnlistptail->next = nullptr;}else{returnlistptail->next = node;returnlistptail = returnlistptail->next;}}if(carry == 1)//当我们每次使用进位后都会将carry重置为0，而此时代表链表一和链表二都遍历完毕，但是还有一次进位没使用，所以要多加一位//例如链表1为999，链表2为 1，此时必须多创建一个节点，用以进位{ListNode *node = new ListNode(1, nullptr);returnlistptail->next = node;   }return returnlistPhead;}
};

代码二：

此处主要是将上面的代码简化。

struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){if (l1 == nullptr) // 如果第一个链表为空，则返回第二个链表{return l2;}if (l2 == nullptr) // 如果第二个链表为空，则返回第一个链表{return l1;}ListNode *prevreturnPhead = new ListNode(-1,nullptr); // 先创建返回链表的头节点链表的前一个节点ListNode *prevreturntail = prevreturnPhead;int carry = 0; // 代表进位while (l1 || l2 || carry){int sum = 0;if (l1){sum += l1->val;l1 = l1->next;}if (l2){sum += l2->val;l2 = l2->next;}sum += carry;prevreturntail->next = new ListNode((sum % 10),nullptr);prevreturntail = prevreturntail->next;carry = sum /10;}return prevreturnPhead->next;}
};

题3：删除链表的倒数第n个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

难度：中等

 3.1方法一：递归

使用cur标志位找到倒数要删除的节点，如果是要删除的节点，则将当前节点的next指针指向下一个节点的next指针，如果不是要删除的节点，则指针保持不变。

注意在递归调用中指针名称相同，但其代表的含义是不同的。

class Solution
{
public:int cur = 0;ListNode *removeNthFromEnd(ListNode *head, int n){if (!head)return NULL;head->next = removeNthFromEnd(head->next, n);cur++;if (n == cur)return head->next;return head;}
};

3.2 方法二：栈

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

第一步：添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。

第二步：将其循环放入栈中。

第三步：找到要删除的元素的上一个元素，即栈顶元素。

第四步：重置要删除的元素的上一个元素的next指针为删除元素的next指针。

第五步：返回哑节点的next指针，即为链表的头结点。

struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:int cur = 0;ListNode *removeNthFromEnd(ListNode *head, int n){if (head == nullptr || n <= 0){return nullptr;}ListNode *dummynode = new ListNode(0, head);//添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了ListNode *dummynode2 = dummynode;stack<ListNode *> stacklists;while (dummynode2 != nullptr){stacklists.push(dummynode2);dummynode2 = dummynode2->next;}while (n != 0 && !stacklists.empty()){n--;stacklists.pop();}ListNode *prevnode = stacklists.top();//要删除节点的上一个节点prevnode->next = prevnode->next->next;ListNode *returnhead = dummynode->next;return returnhead;}
};

题4：两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

思路：

第一步：创建哑结点 dummy，令 dummy.next = head。令 temp 表示当前到达的节点，初始时 temp = dummy。每次需要交换 temp 后面的两个节点。

如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得 temp 后面的两个节点 node1 和 node2，通过更新节点的指针关系实现两两交换节点。

第二步：交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1

temp.next = node2
node1.next = node2.next
node2.next = node1
完成上述操作之后，节点关系即变成 temp -> node2 -> node1。

第三步：再令 temp = node1，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。

两两交换链表中的节点之后，新的链表的头节点是 dummyHead.next，返回新的链表的头节点即可。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:ListNode *swapPairs(ListNode *head){if (head == nullptr || head->next == nullptr){return head;}ListNode *dummy = new ListNode(0, head);//创建一个哑节点，因为除了链表首两个节点交换，其他节点交换会有三个节点的指针发生变化。//所以为了不特殊处理头节点，创建了哑节点。ListNode *temp = dummy;while (temp->next != nullptr && temp->next->next != nullptr)//当哑结点的下一个元素和下两个元素都不为空的时候，才发生交换//{ListNode *one = temp->next;//第一个节点ListNode *two = temp->next->next;//第二个节点temp->next = two;one->next = two->next;two->next = one;temp = one;}ListNode *retrunhead= dummy->next;delete dummy;return retrunhead;}
};

题5：删除排序链表中重复的元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

思路：

本题可以用快慢指针的方法，将慢指针指向第一个节点，快指针指向第二个节点，如果第一个节点的值等于第二个节点的值，则删除当前节点，并移动快指针到下一个值，如果慢指针和快指针指向的值不相等，则慢指针和快指针都向前移动一次，直到遍历完链表。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:ListNode *deleteDuplicates(ListNode *head){if (head == nullptr || head->next == nullptr)//如果链表中没有元素或者只有一个元素则直接返回{return head;}ListNode *slow = head;ListNode *fast = head->next;while (fast != nullptr){if (slow->val == fast->val)//如果慢指针的值等于快指针的值，则删除当前节点，慢指针的下一个节点指向要删除节点的下一个节点{slow->next = fast->next;fast = fast->next;//更新快指针为要删除节点的下一个节点}else //如果慢指针的值不等于快指针的值，则移动慢指针的值到下一位，移动快指针的值也到下一位{slow =slow->next;fast = fast->next;}}return head;}
};

http://www.ppmy.cn/ops/131930.html

相关文章

爬虫-------字体反爬

爬虫-------字体反爬

目录 一、了解什么是字体加密 二. 定位字体位置 三. python处理字体 1. 工具库 2. 字体读取 3. 处理字体 案例1：起点 案例2：字符偏移： 5请求数据 - 发现偏移量 5.4 多套字体替换 套用模板 版本1 版本2 四.项目实战 1. 采集目标 2. 逆向结果 一、了解什么是…
阅读更多...
qt QTextCursor详解

qt QTextCursor详解

1、概述 QTextCursor是Qt框架中用于在QTextDocument或QTextEdit中编辑和导航文本的类。它提供了对文本选择和编辑操作的低级控制&#xff0c;允许插入、删除、修改文本以及改变文本的格式。QTextCursor可以看作是一个在文本中移动的插入点或选择区域&#xff0c;通过它可以执行…
阅读更多...
微信小程序uniapp基于Android的流浪动物管理系统 70c3u

微信小程序uniapp基于Android的流浪动物管理系统 70c3u

文章目录 项目介绍具体实现截图技术介绍mvc设计模式小程序框架以及目录结构介绍错误处理和异常处理java类核心代码部分展示详细视频演示源码获取 项目介绍 以往流浪猫狗的救助网站相关信息的管理&#xff0c;都是工作人员手工统计。这种方式不但时效性低&#xff0c;而且需要查…
阅读更多...
G1垃圾回收器日志详解

G1垃圾回收器日志详解

新生代收集 GC pause (G1 Evacuation Pause) (young) -- gc前堆内存分布情况 {Heap before GC invocations1592 (full 4):garbage-first heap total 6291456K, used 5011297K [0x0000000640000000, 0x0000000640206000, 0x00000007c0000000) --表示使用了G1,堆大小&…
阅读更多...
25国考照片处理器使用流程图解❗

25国考照片处理器使用流程图解❗

1、打开“国家公务员局”网站&#xff0c;进入2025公务员专题&#xff0c;找到考生考务入口 2、点击下载地址 3、这几个下载链接都可以 4、下载压缩包 5、解压后先看“使用说明”&#xff0c;再找到“照片处理工具”双击。 6、双击后会进入这样的界面&#xff0c;点击&…
阅读更多...
oracle 9i 使用dbms_obfuscation_toolkit加密解密

oracle 9i 使用dbms_obfuscation_toolkit加密解密

加密(encrypt)解密(decrypt)采用 Oracle DBMS_OBFUSCATION_TOOLKIT package. 利用这个包,我们可以对数据进行DES,Triple DES或者MD5加密. DESGETKEY --产生密钥,用于DES算法 DES3GETKEY -- 产生密钥,用于Triple DES算法 DESENCRYPT -- 用DES算法加密数据 DESDECRYP…
阅读更多...
SpringBoot中的注解详解（二）

SpringBoot中的注解详解（二）

四、Param() &#xff08;mapper包 Dao层&#xff09; Param()&#xff1a; 功能&#xff1a; 用于在Mapper接口的方法参数上标记参数名称&#xff0c;以便在SQL语句中引用这些参数。 参数命名&#xff1a;在Mapper接口的方法参数上使用Param注解&#xff0c;可以为参数指定一…
阅读更多...
基于SpringBoot的速食零食商城+LW示例参考

基于SpringBoot的速食零食商城+LW示例参考

1.项目介绍 功能模块&#xff1a;管理端&#xff08;用户管理、账号管理、商品分类管理、商品信息管理、订单管理等&#xff09;&#xff0c;用户端&#xff08;商品信息、登录注册、我的订单等&#xff09;技术栈&#xff1a;SpringBoot&#xff0c;thymeleaf&#xff0c;MyB…
阅读更多...
最新文章

Copyright @ 2022~2023