leetcode刷题(2):链表

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, val=0, next=None):# self.val = val# self.next = nextclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional[ListNode]:t1=[]cur=l1# 正确遍历：只要当前节点不为空就取valwhilecur:t1.append(cur.val)cur=cur.next# 指针后移t2=[]cur=l2whilecur:t2.append(cur.val)cur=cur.nextstr1=''.join([str(x)forxint1[::-1]])str2=''.join([str(x)forxint2[::-1]])total=int(str1)+int(str2)# 构造链表，题目要求低位在前，所以反转字符串遍历dummy=ListNode()p=dummy# str(num)是正序数字，反转后低位先入链表 ,为什么要加str，因为数字没法切片forcinstr(total)[::-1]:p.next=ListNode(int(c))p=p.nextreturndummy.next

1. 3 c++ 实现

• 解题1：

class Solution{public:ListNode*addTwoNumber(ListNode*l1,ListNode*l2){ListNode*dummy=newListNode(-1);ListNode p=dummy;bool carry=false;while(l1||l2){intsum=0;if(l1!=nullptr){sum+=l1->val;l1=l1->next;}if(l2!=nullptr){sum+=l2->val;l2=l2->next;}if(carry){sum++;}p->next=newListNode(sum%10);p=p->next;if(sum>10){carry=true;}else{carry=false;}}if(sum>10){p->next=newListNode(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*dummy=newListNode(-1);ListNode*p=dummy;intt=0;while(l1||l2||t){if(l1){t+=l1->val;l1=l1->next;}if(l2){t+=l2->val;l2=l2->next;}p->next=newListNode(t%10);p=p->next;t=t/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(head==nullptr||head->next==nullptr)returnnullptr;ListNode*dummy=newListNode(-1);dummy->next=head;ListNode*p=dummy;while(p->next&&p->next->next){if(p->next->val==p->next->next->val){intx=p->next->val;while(p->next&&p->next->val==x){p->next=p->next->next;}}else{p=p->next;}}returndummy->next;}};

3 旋转链表

对应为leetcode 61题，中等难度。
题目给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例:

3.1 解题思路

• 移动k个位置，计算旋转数据
• 利用旋转数据，构建链表

参考：LeetCode-轮转数组的三种方法（189）

3.2 c++ 实现

• 解题1(击败55%)

class Solution{public:voidreverse(vector<int>&nums,intleft,intright){while(left<right){inttmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}}ListNode*rotateRight(ListNode*head,intk){if(head==nullptr)returnnullptr;ListNode*dummy=newListNode(-1);ListNode*p=dummy;vector<int>res;while(head){res.push_back(head->val);head=head->next;}intlen=res.size();reverse(res,0,len-1);reverse(res,0,k%len-1);reverse(res,k%len,len-1);for(autoval:res){p->next=newListNode(val);p=p->next;}returndummy->next;}};

• 解题2(击败88.54%)

每旋转一次，得到的新数组：
数组中第一个元素，为原来最后一个元素
数组中1-len-1的元素，对应原来0-(len-2)元素，相当于对原来0~len-2元素向右平移1次

class Solution{public:// void reverse(vector<int>&nums,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(vector<int>&nums,intk){for(inti=0;i<k%nums.size();i++){inttemp=nums[nums.size()-1];for(intj=nums.size()-2;j>=0;j--){nums[j+1]=nums[j];}nums[0]=temp;}}ListNode*rotateRight(ListNode*head,intk){if(head==nullptr)returnnullptr;ListNode*dummy=newListNode(-1);ListNode*p=dummy;vector<int>res;while(head){res.push_back(head->val);head=head->next;}intlen=res.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->next=newListNode(val);p=p->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:vector<int>reversePrint(ListNode*head){vector<int>res;while(head){res.push_back(head->val);head=head->next;}reverse(res.begin(),res.end());returnres;}};

5 剑指 Offer 24. 反转链表

题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
== 示例==:

输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL

5.1 解题思路

5.2 c++实现

class Solution{public:ListNode*reverseList(ListNode*head){vector<int>res;ListNode*p=head;ListNode*q=head;while(p){res.push_back(p->val);p=p->next;}reverse(res.begin(),res.end());for(inti=0;i<res.size();i++){q->val=res[i];q=q->next;}returnhead;}};

21. 合并两个有序链表

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
== 示例==：

解题思路

• 新链表是通过拼接给定的两个链表的所有节点组成的，所以不能单纯用值来构建链表，而是需要基于两个链表的节点构建
• 如果两个链表都非空，比较两个链表的值，将值小的节点，赋给新的节点
• 随着遍历，其中一个链表为空，另一个为非空，此时将非空的链表节点，分配给新链表

c++ 实现

class Solution{public:/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ListNode*Merge(ListNode*pHead1,ListNode*pHead2){// write code hereListNode*dummy=newListNode(-1);ListNode*p=dummy;while(pHead1&&pHead2){if(pHead1->val<pHead2->val){p->next=pHead1;pHead1=pHead1->next;p=p->next;}else{p->next=pHead2;pHead2=pHead2->next;p=p->next;}}if(pHead1){p->next=pHead1;}if(pHead2){p->next=pHead2;}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(head==nullptr){returnhead;}ListNode*dummyHead=newListNode(0);dummyHead->next=head;ListNode*lastSorted=head;ListNode*curr=head->next;while(curr!=nullptr){if(lastSorted->val<=curr->val){lastSorted=lastSorted->next;}else{ListNode*prev=dummyHead;while(prev->next->val<=curr->val){prev=prev->next;}lastSorted->next=curr->next;curr->next=prev->next;prev->next=curr;}curr=lastSorted->next;}returndummyHead->next;}};

19. 删除链表的倒数第 N 个结点

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

解题思路

这道题目的考点:

• (1) 如何一次扫描找到倒数第N个节点
• (2)如何删除当前节点(包含：只有当前节点，并没有前继节点，此情况无法通过改变前继节点的next来删除当前节点)

（1）解决如何一次扫描得到倒数第N个节点

使用间隔N个节点双指针，一同向前移动，右边的指针到达尾端，左边指针指向的节点就是倒数第N个节点。

（2 ）删除当前节点的办法

• 方法1：一般删除一个节点，通过将前一个节点的next指向当前节点的next来实现（如果当前节点没有前继节点，则无法通过该方法删除节点)。

pre->next=cur->next;

• 方法2：通过复制下一个节点的值给当前要删的节点， 此时把当前指针作为前继指针，改变它的next指向，然后删除掉下一个指针。该方法不仅可以删除当前节点，同时针对当前节点没有前继节点的情况，也同样适用。

cur->val=cur->next->val;cur->next=cur->next->next;

• 因此，针对要删除节点的next为空的情况，采用方法1进行删除节点，其他情况采用方法2来删除节点(方法2需要next不为空)
  

c++实现

class Solution{public:ListNode*removeNthFromEnd(ListNode*head,intn){if(head->next==nullptr)returnnullptr;// 初始化l_node 和 r_nodeListNode*l_node=head;ListNode*r_node=head;ListNode*l_pre=nullptr;// 1. 移动右节点，使得左右节点间间隔N个节点。for(inti=0;i<n;i++){r_node=r_node->next;}// 2. 同时移动左右节点// 当右节点达到链表尾部，此时左节点就是我们需要找的倒数第N个节点while(r_node!=nullptr){l_pre=l_node;l_node=l_node->next;r_node=r_node->next;}// 3. 当要被删除的节点，next节点为nullptr， 通过 pre->next = cur->next方式删除if(l_node->next==nullptr){l_pre->next=l_node->next;}// 3. 当要被删除的节点，存在next节点时， 此时通过将next节点的值复制到当前节点，然后删除next节点else{l_node->val=l_node->next->val;l_node->next=l_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*pre=nullptr;ListNode*cur=head;while(cur){ListNode*next=cur->next;// 保存，不然会被下一行的pre 覆盖cur->next=pre;pre=cur;// 移动precur=next;// 移动cur}returnpre;}};