文章目录1. 两数相加1.1 解题思路1.2 python 实现1. 3 c 实现2 删除排序链表中的重复元素 ||2.1 解题思路2.2 c 实现3 旋转链表3.1 解题思路3.2 c 实现4 剑指 Offer 06: 从尾到头打印链表4.1 解题思路4.2 c 实现5 剑指 Offer 24. 反转链表5.1 解题思路5.2 c实现21. 合并两个有序链表解题思路c 实现147. 对链表进行插入排序解题思路c实现19. 删除链表的倒数第 N 个结点解题思路c实现114. 二叉树展开为链表BM1 反转链表解题思路c 实现1. 两数相加题目给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储 一位 数字。要求请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。提示每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零1.1 解题思路要求: 返回一个新链表存储两个逆序的链表之和返回的新链表也是逆序排列思路从链表的头开始按位加就可以计算出结果根据加法原则对应位置的计算结果为两数之和对10取余数同时 两数之和与10相除取整为向前进位的数字。1.2 python 实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:t1[]curl1# 正确遍历只要当前节点不为空就取valwhilecur:t1.append(cur.val)curcur.next# 指针后移t2[]curl2whilecur:t2.append(cur.val)curcur.nextstr1.join([str(x)forxint1[::-1]])str2.join([str(x)forxint2[::-1]])totalint(str1)int(str2)# 构造链表题目要求低位在前所以反转字符串遍历dummyListNode()pdummy# str(num)是正序数字反转后低位先入链表 ,为什么要加str因为数字没法切片forcinstr(total)[::-1]:p.nextListNode(int(c))pp.nextreturndummy.next1. 3 c 实现解题1class Solution{public:ListNode*addTwoNumber(ListNode*l1,ListNode*l2){ListNode*dummynewListNode(-1);ListNode pdummy;bool carryfalse;while(l1||l2){intsum0;if(l1!nullptr){suml1-val;l1l1-next;}if(l2!nullptr){suml2-val;l2l2-next;}if(carry){sum;}p-nextnewListNode(sum%10);pp-next;if(sum10){carrytrue;}else{carryfalse;}}if(sum10){p-nextnewListNode(1);}returndummy-next;}}改进版/** * Definition for singly-linked list. * 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){//1. 创建一个dummy节点ListNode*dummynewListNode(-1);ListNode*pdummy;intt0;while(l1||l2||t){if(l1){tl1-val;l1l1-next;}if(l2){tl2-val;l2l2-next;}p-nextnewListNode(t%10);pp-next;tt/10;}returndummy-next;}};2 删除排序链表中的重复元素 ||对应为leetcode 82题中等难度。题目 给定一个已排序的链表的头head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回已排序的链表。示例提示链表中节点数目在范围 [0, 300] 内-100 Node.val 100题目数据保证链表已经按升序 排列2.1 解题思路链表已排序重复元素都是连续的找到两个值相同的连续节点p1,p2假设值都为x遍历节点如果节点p-next值等于x(因为p为dummy节点所以从p-next开始遍历)则删除该节点p-next p-next-next;2.2 c 实现class Solution{public:ListNode*deleteDuplicates(ListNode*head){if(headnullptr||head-nextnullptr)returnnullptr;ListNode*dummynewListNode(-1);dummy-nexthead;ListNode*pdummy;while(p-nextp-next-next){if(p-next-valp-next-next-val){intxp-next-val;while(p-nextp-next-valx){p-nextp-next-next;}}else{pp-next;}}returndummy-next;}};3 旋转链表对应为leetcode 61题中等难度。题目给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。示例:3.1 解题思路移动k个位置计算旋转数据利用旋转数据构建链表参考LeetCode-轮转数组的三种方法1893.2 c 实现解题1(击败55%)class Solution{public:voidreverse(vectorintnums,intleft,intright){while(leftright){inttmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}}ListNode*rotateRight(ListNode*head,intk){if(headnullptr)returnnullptr;ListNode*dummynewListNode(-1);ListNode*pdummy;vectorintres;while(head){res.push_back(head-val);headhead-next;}intlenres.size();reverse(res,0,len-1);reverse(res,0,k%len-1);reverse(res,k%len,len-1);for(autoval:res){p-nextnewListNode(val);pp-next;}returndummy-next;}};解题2(击败88.54%)每旋转一次得到的新数组数组中第一个元素为原来最后一个元素数组中1-len-1的元素对应原来0-(len-2)元素相当于对原来0~len-2元素向右平移1次class Solution{public:// void reverse(vectorintnums,int left,int right)// {// while(left right)// {// int tmp nums[left];// nums[left] nums[right];// nums[right] tmp;// left;// right--;// }// }// 每旋转一次得到的新数组数组中第一个元素为原来最后一个元素// 数组中1-len-1的元素对应原来0~len-2元素相当于对原来0~len-2元素向右平移1次voidrotate3(vectorintnums,intk){for(inti0;ik%nums.size();i){inttempnums[nums.size()-1];for(intjnums.size()-2;j0;j--){nums[j1]nums[j];}nums[0]temp;}}ListNode*rotateRight(ListNode*head,intk){if(headnullptr)returnnullptr;ListNode*dummynewListNode(-1);ListNode*pdummy;vectorintres;while(head){res.push_back(head-val);headhead-next;}intlenres.size();rotate3(res,k);// reverse(res,0,len-1);// reverse(res,0,k%len-1);// reverse(res,k%len,len-1);for(autoval:res){p-nextnewListNode(val);pp-next;}returndummy-next;}};4 剑指 Offer 06: 从尾到头打印链表题目输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。示例示例1 输入head[1,3,2]输出[2,3,1]4.1 解题思路获得链表所有的值利用reverse反转4.2 c 实现/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution{public:vectorintreversePrint(ListNode*head){vectorintres;while(head){res.push_back(head-val);headhead-next;}reverse(res.begin(),res.end());returnres;}};5 剑指 Offer 24. 反转链表题目定义一个函数输入一个链表的头节点反转该链表并输出反转后链表的头节点。 示例:输入:1-2-3-4-5-NULL输出:5-4-3-2-1-NULL5.1 解题思路5.2 c实现class Solution{public:ListNode*reverseList(ListNode*head){vectorintres;ListNode*phead;ListNode*qhead;while(p){res.push_back(p-val);pp-next;}reverse(res.begin(),res.end());for(inti0;ires.size();i){q-valres[i];qq-next;}returnhead;}};21. 合并两个有序链表题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 示例解题思路新链表是通过拼接给定的两个链表的所有节点组成的所以不能单纯用值来构建链表而是需要基于两个链表的节点构建如果两个链表都非空比较两个链表的值将值小的节点赋给新的节点随着遍历其中一个链表为空另一个为非空此时将非空的链表节点分配给新链表c 实现class Solution{public:/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类 */ListNode*Merge(ListNode*pHead1,ListNode*pHead2){// write code hereListNode*dummynewListNode(-1);ListNode*pdummy;while(pHead1pHead2){if(pHead1-valpHead2-val){p-nextpHead1;pHead1pHead1-next;pp-next;}else{p-nextpHead2;pHead2pHead2-next;pp-next;}}if(pHead1){p-nextpHead1;}if(pHead2){p-nextpHead2;}returndummy-next;}};147. 对链表进行插入排序题目:给定单个链表的头 head 使用 插入排序 对链表进行排序并返回 排序后链表的头 。插入排序 算法的步骤:插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。重复直到所有输入数据插入完为止。示例解题思路插入排序的基本思想是维护一个有序序列初始时有序序列只有一个元素每次将一个新的元素插入到有序序列中将有序序列的长度增加1直到全部元素都加入到有序序列中。对链表进行插入排序的具体过程如下。首先判断给定的链表是否为空若为空则不需要进行排序直接返回。创建哑节点 dummyHead令dummyHead-next head。引入哑节点是为了便于在 head 节点之前插入节点。维护 lastSorted 为链表的已排序部分的最后一个节点初始时 lastSorted head。维护curr为待插入的元素初始时curr head-next。比较 lastSorted 和 curr 的节点值。若 lastSorted-val curr-val说明 curr 应该位于 lastSorted 之后将 lastSorted后移一位curr 变成新的 lastSorted。否则从链表的头节点开始往后遍历链表中的节点寻找插入 curr 的位置。令 prev 为插入 curr的位置的前一个节点进行如下操作完成对 curr 的插入c实现/** * Definition for singly-linked list. * 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*insertionSortList(ListNode*head){if(headnullptr){returnhead;}ListNode*dummyHeadnewListNode(0);dummyHead-nexthead;ListNode*lastSortedhead;ListNode*currhead-next;while(curr!nullptr){if(lastSorted-valcurr-val){lastSortedlastSorted-next;}else{ListNode*prevdummyHead;while(prev-next-valcurr-val){prevprev-next;}lastSorted-nextcurr-next;curr-nextprev-next;prev-nextcurr;}currlastSorted-next;}returndummyHead-next;}};19. 删除链表的倒数第 N 个结点题目: 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。示例:解题思路这道题目的考点:(1) 如何一次扫描找到倒数第N个节点(2)如何删除当前节点(包含只有当前节点并没有前继节点此情况无法通过改变前继节点的next来删除当前节点)1解决如何一次扫描得到倒数第N个节点使用间隔N个节点双指针一同向前移动右边的指针到达尾端左边指针指向的节点就是倒数第N个节点。2 删除当前节点的办法方法1一般删除一个节点通过将前一个节点的next指向当前节点的next来实现如果当前节点没有前继节点则无法通过该方法删除节点)。pre-nextcur-next;方法2通过复制下一个节点的值给当前要删的节点 此时把当前指针作为前继指针改变它的next指向然后删除掉下一个指针。该方法不仅可以删除当前节点同时针对当前节点没有前继节点的情况也同样适用。cur-valcur-next-val;cur-nextcur-next-next;因此针对要删除节点的next为空的情况采用方法1进行删除节点其他情况采用方法2来删除节点(方法2需要next不为空)c实现class Solution{public:ListNode*removeNthFromEnd(ListNode*head,intn){if(head-nextnullptr)returnnullptr;// 初始化l_node 和 r_nodeListNode*l_nodehead;ListNode*r_nodehead;ListNode*l_prenullptr;// 1. 移动右节点使得左右节点间间隔N个节点。for(inti0;in;i){r_noder_node-next;}// 2. 同时移动左右节点// 当右节点达到链表尾部此时左节点就是我们需要找的倒数第N个节点while(r_node!nullptr){l_prel_node;l_nodel_node-next;r_noder_node-next;}// 3. 当要被删除的节点next节点为nullptr 通过 pre-next cur-next方式删除if(l_node-nextnullptr){l_pre-nextl_node-next;}// 3. 当要被删除的节点存在next节点时 此时通过将next节点的值复制到当前节点然后删除next节点else{l_node-vall_node-next-val;l_node-nextl_node-next-next;}returnhead;}};114. 二叉树展开为链表题目: 给你二叉树的根结点root请你将它展开为一个单链表展开后的单链表应该同样使用TreeNode其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树先序遍历顺序相同。 示例:BM1 反转链表解题思路(1) 先把下一个节点记下来不然会弄丢(2) 让当前节点反过来指向 pre(3) pre 和 cur 一起往前走(4) 遍历结束pre 就是反转后的新链表头。c 实现/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */class Solution{public:/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param head ListNode类 * return ListNode类 */ListNode*ReverseList(ListNode*head){// write code hereListNode*prenullptr;ListNode*curhead;while(cur){ListNode*nextcur-next;// 保存不然会被下一行的pre 覆盖cur-nextpre;precur;// 移动precurnext;// 移动cur}returnpre;}};