Leetcode链表题目总结
Leetcode链表题目总结
刷题是应届生找工作不可缺少的部分，一种公认的刷题策略是按类别刷题，可是每个类别也有许多题，在有限的时间里到底该刷哪些题呢？个人根据LeetCode官方给出的每个题目的出现频率，整理并收录了每个类别里高频出现的题目，对于官方统计频率太低的题目，不予收录。
- [题目描述](https://cloud.tencent.com/developer)最近刷了一些链表相关的题目，总结了下比较经典的题目。在leetcode中，官方给出的说明是malloc的内存不需要释放，所以代码中都没有free。但是在实际的编程中，我们要将申请的内存释放掉，同时把指针指向NULL，这是一种良好的习惯。
876.链表的中间结点
题目描述
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1： 输入：1,2,3,4,5 输出：此列表中的结点 3(序列化形式：3,4,5) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 3,4,5)。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 输入：1,2,3,4,5,6 输出：此列表中的结点 4 (序列化形式：4,5,6) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。 提示：给定链表的结点数介于 1 和 100 之间。
解题思路
这是一个典型的双指针问题，定义一个快指针，一个慢指针。快指针一次走两步，慢指针一次走一步。当快指针走到结尾时，慢指针指向的就是中间节点。这里要注意一个细节：题目要求：「两个中间结点的时候，返回第二个中间结点」。此时可以在草稿纸上写写画画，就拿自己的左右手的两根指头同步移动，可以得出：快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。如果题目要求「在两个中间结点的时候，返回第一个中间结点」，此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空。注意体会以上二者的不同之处。
代码实现
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slower = head;
struct ListNode* faster = head;
//注意边界条件
while((faster!=NULL)&&(faster->next!=NULL))
{
faster=faster->next->next;
slower=slower->next;
}
return slower;
}328. 奇偶链表
题目描述
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入:2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明: 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
解题思路
这个题目可以用双指针来解决。定义OddNode和EvenNode代表奇偶链表，分别用来遍历链表。其中OddNode = head，EvenNode = head->next。两个指针同时开始遍历，依次连接遍历的元素。到最后时，分别将奇偶链表连接起来即可。
代码实现
struct ListNode* oddEvenList(struct ListNode* head){
if(head == NULL)
return NULL;
struct ListNode* OddHead = head;
struct ListNode* OddNode = head;
struct ListNode* EvenHead = head->next;
struct ListNode* EvenNode = head->next;
while((EvenNode!=NULL)&&(EvenNode->next!=NULL))
{
OddNode->next = OddNode->next->next;
EvenNode->next = EvenNode->next->next;
OddNode=OddNode->next;
EvenNode=EvenNode->next;
}
//跳出循环时OddNode指在链表的前一个节点,EvenNode指向OddNode的前一个 拼接链表， 循环结束时 oddNode 指向奇数链表最后一个元素
OddNode -> next = EvenHead;
return OddHead;
}面试题 02.06. 回文链表
题目描述
编写一个函数，检查输入的链表是否是回文的。
示例 1： 输入： 1->2 输出： false 示例 2： 输入： 1->2->2->1 输出： true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
利用双指针找到链表的中间位置，然后将后半段反转，将后半段依次与前半段比较。
代码实现
bool isPalindrome(struct ListNode* head){
struct ListNode* slow = head;
struct ListNode* fast = head;
struct ListNode* p = head;
while((fast!=NULL) &&(fast->next!=NULL))
{
slow = slow->next;
fast = fast->next->next;
}
struct ListNode *cur = slow;
struct ListNode *pre = NULL;
//将链表的后半段反转
while(cur!=NULL){
//保存下一个的值
struct ListNode* temp = cur->next;
//重新连接当前节点
cur->next = pre;
//更新pre
pre = cur;
//cur指向下一个
cur = temp;
}
// 将后半段反转的链表与前半段依次比较
while(pre&&head){
if(pre->val!=head->val)
return false;
pre=pre->next;head=head->next;
}
return true;
}1290.二进制链表转整数
题目描述
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
示例 1：
输入：head = 1,0,1
输出：5
解释：二进制数(101) 转化为十进制数 (5)
解题思路
将二进制数转换为10进制数的公式为：2n-1 + 2n-2+ …+2n-0(其中n为链表长度)。比如，将1001011转换为10进制数为：1 * 26+0 * 25+0 * 24+1 * 23+0 * 22+1 * 21+1 * 20 = 75。所以，我们只要遍历链表，编程实现这个公式就可以。
代码实现
int getDecimalValue(struct ListNode* head){
int cnt=0;
int data = 0;
struct ListNode* p =head;
//计算链表长度
while(p)
{
p = p->next;
cnt++;
}
//注意长度要减一
cnt = cnt -1;
//从高位开始计算
for(;cnt>=0;cnt--)
{
data += head->val*pow(2,cnt);
head = head->next;
}
return data;
}24.反转链表
题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制：0 <= 节点个数 <= 5000
解题思路
反转链表实际就是重新指向结构体中的next指针，我们需要修改下一个节点的next指针指向前一个节点。所以，在遍历链表时我们要逐个修改链表的指针指向。这个题目也可以用递归来做，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作head .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转。当递归函数全部出栈后，链表反转完成。
代码实现
非递归
struct ListNode* reverseList(struct ListNode* head){
//判断节点长度
if(head == NULL || head->next == NULL)
return head;
else
{
struct ListNode* former = NULL;
struct ListNode* mid = head;
struct ListNode* latter = NULL;
while(mid != NULL)
{
//保存下一个节点
latter = mid->next;
//让该节点指向上一个节点
mid->next = former;
//上一个节点走到当前节点
former = mid;
//当前节点走到下一个节点
mid = latter;
}
return former;
}
/*
if(head == NULL || head->next == NULL)
return head;
//注意pre的初始值
struct ListNode* pre = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;*/递归版本
struct ListNode* reverseList(struct ListNode* head){
//递归版本
if(head == NULL || head->next == NULL){
return head;
}else{
//保存头节点
struct ListNode* mid = head;
//保存下一个节点
struct ListNode* latter = mid->next;
//递归到最后一个几点,返回转置后链表的地址
head = reverseList(latter);
//让后面的节点指向前一个节点
latter->next = mid;
//每次递归返回都赋值为空，最后一次返回将转置后的节点的next赋值为空
mid->next = NULL;
return head;
}
}面试题 02.07. 链表相交
题目描述
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例 1： 输入：intersectVal = 8, listA = 4,1,8,4,5, listB = 5,0,1,8,4,5, skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 4,1,8,4,5，链表 B 为 5,0,1,8,4,5。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 示例 2： 输入：intersectVal = 2, listA = 0,9,1,2,4, listB = 3,2,4, skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 0,9,1,2,4，链表 B 为 3,2,4。在 A中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 示例 3： 输入：intersectVal = 0, listA = 2,6,4, listB = 1,5, skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 2,6,4，链表 B 为 1,5。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。 注意： 如果两个链表没有交点，返回 null 。 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
解题思路
根据题意,两个链表相交的点是指: 两个指针指向的内容相同,则说明该结点记在A链表上又在B链表上,进而说明A和B是相交的
而对于相交的情况,两条链表一定是这种结构:
为什么呢?
因为如果链表A和链表B相交于D的话,那么说明D结点即在A上又在B上,而D之后的元素自然也就均在A和B上了,因为他们是通过next指针相连的.
如果有相交的结点D的话,每条链的头结点先走完自己的链表长度,然后回头走另外的一条链表,那么两结点一定为相交于D点,因为这时每个头结点走的距离是一样的,都是 AD + BD + DC,而他们每次又都是前进1,所以距离相同,速度又相同,固然一定会在相同的时间走到相同的结点上,即D点。
代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *p=headA;
struct ListNode *q=headB;
while(p!=q)
{
if(p==NULL)
p=headB;
else
p=p->next;
if(q==NULL)
q=headA;
else
q=q->next;
}
return q;
}24.两两交换链表中的节点
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.
解题思路
本题需要两两交换链表中相邻的节点，这说明在在整个过程中都是功能相同的操作，这让我们就很自然的想到使用递归的方式去处理。递归的一个重要思想就是两部分：1.找到最简单的子问题求解，2.其他问题不考虑内在细节，只考虑整体逻辑，那我们现在来设计递归关系。
首先看我们的函数swapPairs
函数作用：两两交换链表中的节点
输入：链表的头结点
输出：操作后的链表的头结点
1.对于本题，首先我们来看最简单的子问题，想要两两交换，最起码得有两个节点吧，所有没有节点或只有一个结点的时候我们就直接返回即可，也就是我们的终止条件。
if((head==NULL) || (head->next==NULL))
return head;2，实现两个节点的重新连接操作。首先我们要先连接第一个节点，前两个节点交换后，第一个节点要连接的是第二个节点的下一个，swapPairs(second->next)返回的是后面子链表交换后的第一个节点，所以直接取second->next进递归函数。最后second 连接 first就完成了。
// first 连接后面交换完成的子链表
first->next = swapPairs(second->next);
// second 连接 first
second->next = first;方法二：普通做法，每次一次连接两个节点，注意要先连接第一个节点。连接完成指向下一个位置即可。
代码实现
递归版本
struct ListNode* swapPairs(struct ListNode* head){
// 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了
if((head==NULL) || (head->next==NULL))
return head;
// 2. 调用单元
// 需要交换的两个节点是 head 和 head.next
struct ListNode* first = head;
struct ListNode* second = head->next;
// first 连接后面交换完成的子链表
first->next = swapPairs(second->next);
// second 连接 first
second->next = first;
// 3. 返回值：返回交换完成的子链表
// seconde 变成了头结点
return second;
}非递归版本
struct ListNode* swapPairs(struct ListNode* head){
//若节点小于2个，直接返回
if(NULL == head || NULL == head->next)
return head;
struct ListNode* first = head;
struct ListNode* second = head->next;
//至少交换一次，返回新头节点指向原head的第二个节点
struct ListNode* newHead = second;
do{
first->next=second->next;
second->next=first;
//移动first位置
first=first->next;
//根据下次是否有足够节点进行交换，决定是将已交换过的节点的next重行指向即将交换的节点，还是直接退出循环
if(first&&first->next){
second->next->next=first->next;
second=first->next;
}else{
break;
}
} while(1);
return newHead;
}面试题 02.01. 移除重复节点
题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1: 输入：1, 2, 3, 3, 2, 1 输出：1, 2, 3 示例2: 输入：1, 1, 1, 1, 2 输出：1, 2 提示： 链表长度在0, 20000范围内。 链表元素在0, 20000范围内。 进阶： 如果不得使用临时缓冲区，该怎么解决？
解题思路
思路一：定义两个指针current和p来逐个遍历链表，current元素依次和p比较，直到p为NULL，current向后移动一个。
思路二：利用标记数组，标记当前值是否出现过
代码实现
方法一：
struct ListNode* removeDuplicateNodes(struct ListNode* head){
//判断是否需要遍历
if (head == NULL) return NULL;
struct ListNode* current = head;
//双指针逐个比较
while (current) {
struct ListNode* p = current;
while(p->next) {
if (p->next->val == current->val) {
p->next = p->next->next;
} else {
p = p->next;
}
}
current = current->next;
}
return head;
}方法二：
struct ListNode* removeDuplicateNodes(struct ListNode* head){
//判断是否需要遍历
if(head==NULL || head->next==NULL)
return head;
//利用val的值在0~20000之间，标记是否出现过
int index[20001] = {0};
index[head->val] = 1;
struct ListNode *pre = head, *q = head->next;
while(q)
{
//当前val未出现过，保存当前val，修改pre和p指针
if(index[q->val]==0)
{
index[q->val] = 1;
pre = q;
q = q->next;
}
//当前值已经出现过了，删除当前节点
else
{
pre->next = q->next;
q = pre->next;
}
}
return head;
}面试题52. 两个链表的第一个公共节点
题目描述
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = 4,1,8,4,5, listB = 5,0,1,8,4,5, skipA
= 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 4,1,8,4,5，链表 B 为 5,0,1,8,4,5。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = 0,9,1,2,4, listB = 3,2,4, skipA = 3,
skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2
（注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 0,9,1,2,4，链表 B 为 3,2,4。在 A中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = 2,6,4, listB = 1,5, skipA = 3, skipB= 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 2,6,4，链表 B 为 1,5。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n)
时间复杂度，且仅用 O(1) 内存。
解题思路
此题和上面面试题 02.07. 链表相交的解法相同，不再赘述。
21. 合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
解题思路
两个链表是排序过得，所以我们只需要同时遍历两个链表，比较链表元素的大小，将小的连接到新的链表中即可。最后，可能有一个链表会先遍历完，此时，我们直接将另一个链表连接到新链表的最后即可。
代码实现
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL)//判空
return l2;
if(l2 == NULL)
return l1;
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* pre= head;
//struct ListNode head;
//struct ListNode *pre = &head;
//先连接小的元素
while (l1 && l2) {
if (l1->val <= l2->val) {
pre->next = l1;
l1 = l1->next;
} else {
pre->next = l2;
l2 = l2->next;
}
pre = pre->next;
}
//将剩下元素直接接在最后面
pre->next = (NULL == l1 ? l2 : l1);
return head->next;
}面试题18. 删除链表的节点
题目描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1: 输入: head = 4,5,1,9, val = 5 输出: 4,1,9 解释: 给定你链表中值为 5的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = 4,5,1,9, val = 1 输出: 4,5,9 解释: 给定你链表中值为 1的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 说明： 题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
解题思路
删除链表的节点，其实就是重新更改next指针的指向，让其跳过要删除的节点即可，因此，我们需要存储待删除节点的前一个元素。当删除的节点为头结点、中间节点、尾节点时需要分别讨论。
1.删除的节点为头结点。定义一个空的节点，里面不存放元素，将next指针指向链表头。我们这个节点可以称作哨兵节点，只起指示作用，不存储元素。删除头结点的话，只需要将哨兵节点的next指针指向要删除节点的下一个即可。（其实也可以不定义哨兵节点，只不过删除起来比较麻烦，参考：史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)）
2.要删除的节点为中间节点时，我们遍历链表时要存储其前一个元素，让其指向删除节点的下一个即可。
3.要删除的节点为尾节点，直接让pre节点指向NULL即可。
代码实现
struct ListNode* deleteNode(struct ListNode* head, int val){
if(head==NULL)
return NULL;
struct ListNode* pre = head;
struct ListNode* p = head;
while(p)
{
if(p->val == val)
{
//删除节点为尾节点
if (p->next == NULL)
{
pre->next =NULL;
return head;
}
//删除节点为头节点
else if (p == head)
{
return head->next;
}
//删除节点为中间节点
else
{
pre->next = p->next;
break;
}
}
//记录下前一个节点
pre = p;
p = p->next;
}
return head;
}哨兵节点
struct ListNode* deleteNode(struct ListNode* head, int val){
if(head==NULL)
return NULL;
struct ListNode* tmphead = (struct ListNode*)malloc(sizeof(struct ListNode));
tmphead->next = head;
//这里是核心，将pre赋值
struct ListNode* pre = tmphead;
struct ListNode* p = head;
while(p)
{
if(p->val == val)
{
pre->next = p->next;
return tmphead->next;
}
pre = p;
p = p->next;
}
return tmphead->next;
}2. 两数相加
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
解题思路
面试题 02.05. 链表求和22 相同
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p1 = l1;
struct ListNode* p2 = l2;
struct ListNode* q = l3;
int carry = 0;
int sum = 0;
while((p1!=NULL) ||(p2!=NULL))
{
sum = 0;
if(p1!=NULL)
{
sum += p1->val;
printf("sum:%d\r\n",sum);
}
if(p2!=NULL)
{
sum += p2->val;
printf("sum:%d\r\n",sum);
}
printf("sum:%d,carry:%d\r\n",sum,carry);
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = sum%10+carry;
carry = (sum>=10)? 1 : 0;
printf("temp->val:%d\r\n",temp->val);
printf("\r\n");
temp->next = NULL;
q->next = temp;
q = temp;
p1 = p1->next;
p2 = p2->next;
}
return l3->next;
}简洁写法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int carry = 0;
struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//设置哨兵节点，记录起始位置
struct ListNode* tmp =l3;
//当carry大于0时，说明还有元素需要存到链表中 比如999+999
while(l1||l2||carry)
{
l3->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l3 = l3->next;
//链表为空时直接赋值0
carry+=((l1==NULL)?0:l1->val)+((l2==NULL)?0:l2->val);
//printf("carry:%d\r\n",carry);
l3->val = carry%10;
//printf("p->val:%d\r\n",p->val);
carry /= 10;
//printf("carry:%d\r\n",carry);
l1 = l1 ? l1->next : 0;
l2 = l2 ? l2->next : 0; // 每次需要判断，因为l1->val取值问题
//printf("\r\n");
}
//加上结束符
l3->next=NULL;
return tmp->next;
}445. 两数相加 II
题目描述
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例： 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
解题思路
1 先将链表1和链表2中的数据存在stack中；
2 从两个栈的栈顶开始取数据，相加，注意需要记录下是否有进位（存在carry变量中），每次都需要将进位一起加进去；
3 当两个栈中有一个为空另一个不为空时，单独处理不为空的；
4 如果都为空，表示数据全部加完；
5 判断进位是否为0，如果为0表示没有进位，如果不为0表示有进位，将进位也需输出。
代码实现
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int stack1[100];
int stack2[100];
int top1 = -1;
int top2 = -1;
int carry = 0;
int sum;
struct ListNode *rlt = (struct ListNode*)malloc(sizeof(struct ListNode) * 1);
//入栈
while (l1 != NULL) {
stack1[++top1] = l1->val;
l1 = l1->next;
}
while (l2 != NULL) {
stack2[++top2] = l2->val;
l2 = l2->next;
}
rlt->next = NULL;
while (top1 >= 0 && top2 >= 0) {
int tmp = stack1[top1--] + stack2[top2--];
sum = (tmp + carry) % 10;
carry = (tmp + carry) / 10;
rlt->val = sum;
/*翻转链表链接 (正向连接为rlt->next = curr rtl = curr)*/
struct ListNode *curr = (struct ListNode*)malloc(sizeof(struct ListNode) * 1);
curr->next = rlt;
rlt = curr;
}
while (top1 >= 0) {
int tmp = stack1[top1--];
sum = (tmp + carry) % 10;
carry = (tmp + carry) / 10;
rlt->val = sum;
struct ListNode *curr = (struct ListNode*)malloc(sizeof(struct ListNode) * 1);
curr->next = rlt;
rlt = curr;
}
while (top2 >= 0) {
int tmp = stack2[top2--];
sum = (tmp + carry) % 10;
carry = (tmp + carry) / 10;
rlt->val = sum;
struct ListNode *curr = (struct ListNode*)malloc(sizeof(struct ListNode) * 1);
curr->next = rlt;
rlt = curr;
}
//进位值需要全部存储，如链表1[5]，链表2[5]，进位为1，我们需要全部存储10.
if (carry != 0) {
rlt->val = carry;
return rlt;
} else {
return rlt->next;
}
}简洁写法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int stack1[100];
int stack2[100];
int top1 = -1;
int top2 = -1;
int carry = 0;
struct ListNode *l3 = (struct ListNode*)malloc(sizeof(struct ListNode));
l3->next =NULL;
//入栈
while (l1 != NULL) {
stack1[++top1] = l1->val;
l1 = l1->next;
}
while (l2 != NULL) {
stack2[++top2] = l2->val;
l2 = l2->next;
}
//循环停止的边界条件
while(top1!=-1 || top2!=-1 ||carry)
{
//当栈为空时，直接赋值为0
carry+=((top1==-1)?0:stack1[top1])+((top2==-1)?0:stack2[top2]);
//printf("carry:%d\r\n",carry);
l3->val = carry%10;
//printf("l3->val:%d\r\n",l3->val);
carry /=10;
//printf("carry:%d\r\n",carry);
//新建节点用于存储l3的内容
struct ListNode *curr = (struct ListNode*)malloc(sizeof(struct ListNode));
//把新建节点的next指针指向l3就实现了反向存储
//如果把l3->next = curr 就是正向存储
curr->next = l3;
//移动l3指针指向curr
l3 = curr;
//防止栈的数组越界
top1 = (top1 == -1)?-1:(top1-1);
top2 = (top2 == -1)?-1:(top2-1);
//printf("top1:%d top2:%d\r\n",top1,top2);
}
return l3->next;
}725. 分隔链表
题目描述
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ 1, 2, 3, 4, null ]
示例 1： 输入: root = 1, 2, 3, k = 5 输出: [1,2,3,[],[]] 解释:输入输出各部分都应该是链表，而不是数组。 例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。 第一个输出 output0是 output0.val = 1, output0.next = null。 最后一个元素 output4 为 null,它代表了最后一个部分为空链表。 示例 2： 输入: root = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, k = 3 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 解释: 输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。 提示: root 的长度范围： 0, 1000. 输入的每个节点的大小范围：0, 999. k 的取值范围： 1, 50.
解题思路
总体思路:类比给k个孩子分N个苹果，先平均分，再把多的从头往后分(实际操作时，是两个部分一起分的，因为要按照原来的顺序分)
1.申请内存(注意是二维指针)[一段连续二维指针，便可写成数组的格式，用下标访问，outputi对应的是第i个链表的表头]
2.遍历链表得到length,算出mod-平均分完后多出来的结点数,size-每个部分本应有的结点数
3.循环 分割链表(注意特殊情况:length<k,k以后的部分都应是NULL)
3中的亮点:curSize的计算
注意点:还有一个 *returnSize 参数需要赋值。 (因为传进来的是指针，直接赋值即可)
代码实现
struct ListNode** splitListToParts(struct ListNode* root, int k, int* returnSize){
//注意申请内存的表达式
struct ListNode** output=(struct ListNode**)malloc(k*sizeof(struct ListNode*));
int length=0;
struct ListNode* cur=root;
while(cur!=NULL)
{
length++;
cur=cur->next;
}
//遍历后不能忘了把指针重置到链表开头/
cur=root;
int mod=length%k;
int size=length/k;
for(int i=0;i<k;i++)
{
//将每一个链表放进指针数组中
output[i]=cur;
//如果i<k但是cur==NULL 那么证明是特殊情况(length<k) 只将cur(即NULL)赋给数组元素 后面的都不执行
if(cur!=NULL)
{
//亮点 每一个子链表的实际大小=节点总数均分后的大小+余下的节点从前往后分
int curSize=size+(mod-- >0? 1:0);
//分割链表
for(int j=0; j<curSize-1; j++) cur=cur->next;
//存下链表节点的下一个位置，断开链表与之前链表的连接
struct ListNode* next=cur->next;
cur->next=NULL;
cur=next;
}
}
//题目中的一个参数(用来返回链表个数？？？)
*returnSize=k;
return output;
}面试题 02.08. 环路检测
题目描述
给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
示例 1： 输入：head = 3,2,0,-4, pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = 1,2, pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = 1,pos = -1 输出：no cycle 解释：链表中没有环。 进阶： 你是否可以不用额外空间解决此题？
解题思路
见下题
142. 环形链表 II
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = 3,2,0,-4, pos = 1 输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = 1,2, pos = 0 输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = 1, pos = -1 输出：no cycle 解释：链表中没有环。
进阶： 你是否可以不用额外空间解决此题？
解题思路
利用两个指针，第一个指针移动一次到下一个节点，第二个指针移动一次到下下个节点。如果该链表是环形链表，那么当两个指针指向同一个节点时，该节点与目标节点的距离（正向）和head节点与目标节点的距离相等。
假设快指针和慢指针相遇时慢指针走了k步，由于快指针比慢指针多走了一圈，所以环的长度为k。不难发现相遇节点与目标节点距离为k-(k-p)即为p,head与目标节点的距离也是p。
假设有两个指针，分别为快慢指针fast和slow, 快指针每次走两步，慢指针每次前进一步，如果有环则两个指针必定相遇；
A:链表起点
B:环起点
C:相遇点
X:环起点到相遇点距离
Y:链表起点到环起点距离
R：环的长度
S:第一次相遇时走过的路程
慢指针slow第一次相遇走过的路程 S1 = Y + X;（11）
快指针fast第一次相遇走过的路程 S2=2S1 = Y + X + NR;（2）
说明：快指针的速度是慢指针的两倍，相同时间内路程应该是慢指针的两倍，Y + X + NR是因为快指针可能经过N圈后两者才相遇；
把（1）式代入（2）式得：Y = NR -X;
表明头节点和C点的慢指针会在B点相遇，此处就是环节点.
扩展：
1.求环长 第一次相遇点到下次相遇时经过的距离
代码实现
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}83. 删除排序链表中的重复元素
题目描述
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3
解题思路
由于是排序链表，我们只需要遍历链表依次两两判断是否重复就可以。
代码实现
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode* cur = head;
while(cur != NULL && cur->next != NULL){
if(cur->val == cur->next->val){
cur->next = cur->next->next;
}
else
cur = cur->next;
}
return head;
}面试题 02.05. 链表求和22
题目描述
;给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例： 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 进阶：假设这些数位是正向存放的，请再做一遍。 示例： 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912
解题思路
1.由于需要原地修改，那么末尾结点前驱节点是必须拿到的（否则你先全部遍历完，然后再取）
2.进位处理，相加取余，最后还需要判断carry=1（这种只可能在链表终止，比如2->4->3,5->6->6)
最短遍历，取到尾结点前驱节点，同时carry进位存储
在上述遍历后，定有其中一个结束或者一起结束，都获得前结点，还要对此结点进行加减操作
判断上步是谁终止，将长的连l1上，然后继续运算。如果一起断，那么最后判断carry=1额外申请结点
代码实现
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *p, *q;
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
q = dummy;
int carry = 0; // 进位
while (l1 || l2 || carry) { // 最长遍历与carry进位1处理
p = (struct ListNode*)malloc(sizeof(struct ListNode));
carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
p->val = carry % 10;
carry /= 10;
l1 = l1 ? l1->next : 0;
l2 = l2 ? l2->next : 0; // 每次需要判断，因为l1->val取值问题
p->next = NULL;
q->next = p; // 1.有dummy直接连接此轮p结点
q = p; // 2.q保存此轮p，到下轮就是p的上节点
}
return dummy->next;
}203. 移除链表元素
题目描述
删除链表中等于给定值 val 的所有节点。
示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
解题思路
之前有一题是依次判断链表是否是头结点，中间节点，尾节点。分情况来讨论。我们可以定义一个哨兵节点，其实也可以不用分情况。
代码实现
struct ListNode* removeElements(struct ListNode* head, int val){
//哨兵节点,置于链表头之前
struct ListNode *swap = malloc(sizeof(struct ListNode));
swap->next = head;
struct ListNode *curr = head, *prev = swap;
while (curr != NULL){ //当前值不为空
if (curr->val == val){
prev->next = curr->next; //删除当前节点
} else{
prev = curr; //否则，向后继续判断，当前节点变成前一个节点
}
curr = curr->next; //下一个节点移到当前节点，继续判断
}
head = swap->next;
free(swap); //判断完毕，释放哨兵节点
return head;
}61. 旋转链表
题目描述
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL
（后续更新）