链表强训
1.前言
LeetCode.92.反转链表（2）
1. 题目
2.思路推导
3. 代码实现
LeetCode.445.两数相加（2）
1. 题目
2. 思路推导
3. 代码实现
LeetCode.1019. 链表中的下一个更大节点
1. 题目
2. 思路推导
3. 代码实现
总结：
1.前言
Hello小伙伴们，最新的刷题章节更新了，本篇文章是对链表的训练，为大家准备了三道题，这三道题在我们之前训练的基础上实现起来不是很困难，当然，如果之前没有训练过的小伙伴们，可以先看这个章节呀：链表总结
那么，在大家已有的基础之上，我们开始对下面的三道oj进行逐一的讲解：
LeetCode.92.反转链表（2）
1. 题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
2.思路推导
在这道题开始之前我们知道反转链表有两种方式，分别是迭代和头插，对于此题，本质上仍然是变式之前的反转链表，只不过有了范围，那我们就将这个范围的链表单拿出来，这里指的单拿出来是将其两端区间断开，并记录新的头，也就是左区间的第一个节点，断开的目的是让在这个区间的链表单独反转，如果不断开或者只断开左面的节点，将会导致区间外的链表节点跟着反转。
- 第一步：将需要反转的链表断开，并记录连接的位置
- 第二步：将断开的链表进行反转（两种方法，此例用的迭代）
- 第三步：连接链表
那么有了大致过程，就可以上代码了
3. 代码实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ // 思路： 将区间两侧的节点记录好，然后将这个区间两侧断开单拿出来反转，反转之后再将其两侧进行连接 struct ListNode* reverse(struct ListNode* head)//反转链表 { struct ListNode* cur = head; struct ListNode* prev = NULL; struct ListNode* next = head->next; while(cur) { cur->next = prev; prev = cur; cur = next; if(next) next = next->next; } return prev; } struct ListNode* reverseBetween(struct ListNode* head, int left, int right){ if(head == NULL || head->next == NULL||left == right) { return head; } struct ListNode* cur = head; struct ListNode* lprev = NULL; struct ListNode* rafter = NULL; //找左端点 while(--left) { lprev = cur; cur = cur->next; } //找右端点 cur = head; while(--right) { cur = cur->next; } //看左端点是否为空，为空代表从第一个节点开始反转 if(lprev) { struct ListNode* reverhead = lprev->next; lprev->next = NULL; struct ListNode* afterhead = cur->next;//afterhead代表rafter cur->next = NULL; struct ListNode* rev = reverse(reverhead); lprev->next = rev; while(rev->next) { rev = rev->next; } rev->next = afterhead; return head; } else { struct ListNode* afterhead = cur->next; cur->next = NULL; struct ListNode* rev = reverse(head); struct ListNode* now = rev; while(now->next) { now = now->next; } now->next = afterhead; return rev; } }
LeetCode.445.两数相加（2）
1. 题目
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0] 输出：[0]
提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
**进阶：**如果输入链表不能翻转该如何解决？
2. 思路推导
将两个链表分别反转之后，就可以遍历两个链表然后相加，不过，我们应该选择一个长的链表为基础，让此节点的 val1 = val1+val2 ,并且应该将这个基础链表再尾插一个新的节点，让这个节点的val=0，目的是为了进位用，然后再将这个长链表反转，如果头（此时的头为新尾插的节点）的val = 0，则free掉这个头，让head指向下一个节点。
- 第一步：反转两个链表
- 第二步：为长的链表增加一个节点，相加
- 第三步：反转回来，并去0
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverse_list(struct ListNode* head) { if(head == NULL||head->next==NULL) return head; struct ListNode* newHead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; } int lenth_list(struct ListNode* head) { struct ListNode* cur = head; int len = 0; while(cur) { cur = cur->next; len++; } return len; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode* rev1 = reverse_list(l1); struct ListNode* rev2 = reverse_list(l2); int large = lenth_list(rev1); int small = lenth_list(rev2); struct ListNode* longth = rev1; struct ListNode* shorth = rev2; if(large<small) { longth = rev2; shorth = rev1; } struct ListNode* cur = longth;//长的 struct ListNode* curs = shorth; while(cur->next) { cur = cur->next; } struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); newnode->val = 0; newnode->next = NULL; cur->next = newnode; cur = longth; int carry = 0; while(cur && curs) { cur->val +=curs->val+carry; if(cur->val>9) { carry = cur->val/10; cur->val %=10; } else { carry = 0; } cur = cur->next; curs = curs->next; } while(cur) { cur->val = cur->val+carry; if(cur->val>9) { carry = cur->val/10; cur->val %=10; } else { carry = 0; } cur = cur->next; } struct ListNode* phead = reverse_list(longth); if(phead->val == 0) { struct ListNode* del = phead; phead = phead->next; free(del); } return phead; }
LeetCode.1019. 链表中的下一个更大节点
1. 题目
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
示例 1：
输入：head = [2,1,5] 输出：[5,5,0]
示例 2：
输入：head = [2,7,4,3,5] 输出：[7,0,5,5,0]
提示：
- 链表中节点数为
n 1 <= n <= 1041 <= Node.val <= 109
2. 思路推导
对于这道题，服从题干的思路即可，即暴力解决，需要注意的是记得将*returnSize 赋值，
*returnSize代表返回元素的个数。
3. 代码实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverse_list(struct ListNode* head) { if(head == NULL||head->next==NULL) return head; struct ListNode* newHead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; } int lenth_list(struct ListNode* head) { struct ListNode* cur = head; int len = 0; while(cur) { cur = cur->next; len++; } return len; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode* rev1 = reverse_list(l1); struct ListNode* rev2 = reverse_list(l2); int large = lenth_list(rev1); int small = lenth_list(rev2); struct ListNode* longth = rev1; struct ListNode* shorth = rev2; if(large<small) { longth = rev2; shorth = rev1; } struct ListNode* cur = longth;//长的 struct ListNode* curs = shorth; while(cur->next) { cur = cur->next; } struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); newnode->val = 0; newnode->next = NULL; cur->next = newnode; cur = longth; int carry = 0; while(cur && curs) { cur->val +=curs->val+carry; if(cur->val>9) { carry = cur->val/10; cur->val %=10; } else { carry = 0; } cur = cur->next; curs = curs->next; } while(cur) { cur->val = cur->val+carry; if(cur->val>9) { carry = cur->val/10; cur->val %=10; } else { carry = 0; } cur = cur->next; } struct ListNode* phead = reverse_list(longth); if(phead->val == 0) { struct ListNode* del = phead; phead = phead->next; free(del); } return phead; }
3. 代码实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ //暴力解决：按着题目要求来即可 int list_size(struct ListNode* head) { if(head == NULL) return 0; struct ListNode* cur = head; int count = 0; while(cur) { cur = cur->next; count++; } return count; } int* nextLargerNodes(struct ListNode* head, int* returnSize){ int len = list_size(head); *returnSize = len; int* arr = (int*)calloc(len,sizeof(int)); int i = 0; struct ListNode* cur = head; while(cur) { struct ListNode* cnext = cur->next; struct ListNode* next = cur->next; if(next!=NULL) { while(next) { if(cur->val<next->val) { arr[i++] = next->val; break; } next = next->next; } if(next == NULL) { arr[i++] = 0; } } else { arr[i++] = 0; } cur = cnext; } return arr; }
总结：
那么这次的文章就到这里，如果对你有帮助的话，记得三连支持一下呀！
