网站服务器的功能,做可转债好的网站,北京网站定制开发,域名停域app免费下载目录 1.leetcode-82. 删除排序链表中的重复元素 II#xff08;1#xff09;题目描述#xff08;2#xff09;方法及思路#xff08;一次遍历#xff09;#xff08;3#xff09;代码实现 2.leetcode-19. 删除链表的倒数第 N 个结点#xff08;1#xff09;题目描述1题目描述2方法及思路一次遍历3代码实现 2.leetcode-19. 删除链表的倒数第 N 个结点1题目描述2方法一双指针3方法二计算链表长度最直观4方法三栈 3.leetcode-83. 删除排序链表中的重复元素1题目描述2方法及思路一次遍历3代码实现 4.leetcode-86. 分隔链表1题目描述2方法及思路模拟3代码实现 5.leetcode-25. K 个一组翻转链表较难1题目描述2方法及思路模拟3代码实现 1.leetcode-82. 删除排序链表中的重复元素 II
1题目描述
给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回 已排序的链表 。
2方法及思路一次遍历
1.我们从指针 prev 指向链表的哑节点随后开始对链表进行遍历。 2.如果当前 cur与 cur.next对应的元素相同那么我们就需要将 cur 以及所有后面拥有相同元素值的链表节点全部删除。 3.我们记下这个元素值 随后不断将 cur从链表中移除 4.如果cur与cur-next对应的元素不相同则将prev指向cur所在位置cur继续往下找。 5.当遍历完整个链表之后我们返回链表的的哑节点的下一个节点 dummy.next即可。 注意哑节点可以不用考虑head就被删的特殊情况
3代码实现
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(headNULL){return NULL;}ListNode* newnodenew ListNode(0);ListNode* prevnewnode;prev-nexthead;ListNode* curhead;while(cur!NULLcur-next!NULL){if(cur-valcur-next-val){int valcur-val;while(cur ! NULL cur-val val){cur cur-next;}prev-nextcur;}else{prevcur;curcur-next;}}return newnode-next;}
};2.leetcode-19. 删除链表的倒数第 N 个结点
1题目描述
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
2方法一双指针
思路 1.先定义一个first指针由于要删掉倒数第n个节点所以可以让first指针先走n步。 2.当first走完在定义一个second指针此时两指针一起走当first走到尾部时second就走到了要删掉的节点的前一位。 3.将second所在节点指向它下一位的下一位即可删掉 注意点first和second从哪里开始走first的终止条件是哪里 first从head出发终止条件是走到空停止 而对于second与第一题中一样引入哑节点second从此处开始走
代码实现
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* newnodenew ListNode(0,head);ListNode* curhead;while(n0){curcur-next;n--;}ListNode* prevnewnode;while(cur){prevprev-next;curcur-next;}prev-nextprev-next-next;return newnode-next;}
};3方法二计算链表长度最直观
思路 一种容易想到的方法是我们首先从头节点开始对链表进行一次遍历得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历当遍历到第 L−n1 个节点时它就是我们需要删除的节点。 代码实现
class Solution {
public:int getLength(ListNode* head) {int length 0;while (head) {length;head head-next;}return length;}ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);int length getLength(head);ListNode* cur dummy;for (int i 1; i length - n 1; i) {cur cur-next;}cur-next cur-next-next;ListNode* ans dummy-next;delete dummy;return ans;}
};4方法三栈
思路 我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则我们弹出栈的第 n 个节点就是需要删除的节点并且目前栈顶的节点就是待删除节点的前驱节点。这样一来删除操作就变得十分方便了。也就是只要找到就直接操作 代码实现
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);stackListNode* stk;ListNode* cur dummy;while (cur) {stk.push(cur);cur cur-next;}for (int i 0; i n; i) {stk.pop();}ListNode* prev stk.top();prev-next prev-next-next;ListNode* ans dummy-next;delete dummy;return ans;}
};3.leetcode-83. 删除排序链表中的重复元素
1题目描述
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
2方法及思路一次遍历
思路具体地我们从指针 cur\textit{cur}cur 指向链表的头节点随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同那么我们就将 cur.next 从链表中移除否则说明链表中已经不存在其它与 cur 对应的元素相同的节点因此可以将 cur 指向 cur.next。
3代码实现
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* cur head;while (cur-next) {if (cur-val cur-next-val) {cur-next cur-next-next;}else {cur cur-next;}}return head;}
};4.leetcode-86. 分隔链表
1题目描述
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。
2方法及思路模拟
思路 直观来说我们只需维护两个链表 small 和 large 即可small 链表按顺序存储所有小于 x 的节点large 链表按顺序存储所有大于等于 x的节点。遍历完原链表后我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。 1.先定义两个哨兵位smallHead和largeHead这样做的目的是为了更方便地处理头节点为空的边界条件。 2.遍历链表找出小的储存进small大的储存进large 3.合并链表时注意large节点的指向并注意要删除largeHead
3代码实现
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* smallnew ListNode(0);ListNode* smallHeadsmall;ListNode* largenew ListNode(0);ListNode* largeHeadlarge;while(head!NULL){if(head-valx){small-nexthead;smallsmall-next;}else{large-nexthead;largelarge-next;}headhead-next;}large-nextNULL;small-nextlargeHead-next;delete largeHead;return smallHead-next;}
};5.leetcode-25. K 个一组翻转链表较难
1题目描述
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。 k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
2方法及思路模拟
思路 1.首先按照k来进行分组每k个会重新是一个head。 2.然后对每k个数进行反转链表。 3.反转完链表要注意头和尾与前后的相连所以在实现反转链表的函数中还要返回头和尾 4.遍历到最后时如果个数少于k就直接返回
3代码实现
首先先实现部分链表反转部分 pairListNode*,ListNode* myReserve(ListNode* head,ListNode* tail){ListNode* prevtail-next;ListNode* phead;while(prev!tail){ListNode* nexp-next;p-nextprev;prevp;pnex;}return {tail,head};}总体部分实现 1.在每次实现完注意要有个prev在head前一开始就是哨兵位prev用来与反转完的部分进行连接。prev更新的位置即使在tail处新head前 2.还要定义一个next在反转链表之前也就是在找到新tail时定义在他的后面用于反转部分尾部的连接
ListNode* reverseKGroup(ListNode* head, int k) {ListNode* hairnew ListNode(0);hair-nexthead;ListNode* prehair;while(head){ListNode* tailpre;for (int i 0; i k; i) {tail tail-next;if (!tail) {return hair-next;}}ListNode* nexttail-next;pairListNode*,ListNode* resultmyReserve(head,tail);headresult.first;tailresult.second; pre-nexthead;tail-nextnext;pretail;headtail-next;}return hair-next;}
