网站建设目标 优帮云,天津设计公司联系方式,备案 个人网站,网站换空间要重新备案吗1. 链表
1.1 题目#xff1a;合并两个有序链表
链表的建立与插入#xff1a;关键在于留出头部#xff0c;创建迭代指针。 ListNode* head new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p 0; // 再创建一个数据…1. 链表
1.1 题目合并两个有序链表
链表的建立与插入关键在于留出头部创建迭代指针。 ListNode* head new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p 0; // 再创建一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodep head; // 把head 里面的地址赋值给p完整的代码 作者小陈写不完代码
链接https://zhuanlan.zhihu.com/p/365219765
来源知乎
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。#includeiostream
#includestring
using namespace std;
struct node
{string name;int score;node* next;
};
node* creatList(); // 创建了一个返回值为指向数据类型为node的执政,即返回的是一个地址
int main()
{node* headcreatList();
}
node* creatList()
{node* head new node; // 通过new 创建了一个数据类型为node的数据 并把该数据的地址赋值给nodenode* p new node; // 再创建一个数据类型为node的数据 并把该数据的地址赋值给nodephead; // 把head 里面的地址赋值给pp-nextNULL; //这里把p指向的数据类型为node的数据里的 指针next指向了空.指针必须有对象 即指向一个地方,你不告诉它 它就乱跑 所以一般都是让它空着while (true) // 这里我选择while循环 因为里面是true 所以会一直进行 ,我们在里面使用条件判断加break跳出来{coutPlease enter student name: ;cinp-name; // 录入学生的姓名coutPlease enter student score: ;cinp-score; // 输入学生的分数if(p-score 0){break; // 如果分数小于0 跳出循环即输入结束.}node*q new node; // 没有跳出循环 即继续输入,这时我们再创建一个这些数据类型为node的数据 并把它的地址赋值给 指针变量 q .p-nextq; // 刚刚p指针指向的数据类型为node的数据里的 指针next 指向 q ,节点p 和 节点q连起来了..q-nextNULL; // 指针q指向的数据类型为node的数据里的指针 next 指针也不能乱指,所以我们让它指向 NULLpq; // 这里我当初就搞了很长时间.还记的嘛 p 和 q 是什么 ,它们两都是指针变量.它们里面放的是地址,而且它们里面的地址是可以给其它的指向相同数据类型的指针的,这里我们把q里面的地址 给了p 这样p里面存放的地址就是这个链表的最后一个节点的地址.如此反复我们就实现了动态输入.}return head; // 这就是为什么我们要设置head了,因为p的地址是不断变化的,而head里面的地址是不变的.而且head里面放的就是第一个节点的地址,
}依据数组创建列表的时候需要考虑到函数内部不好获得数组的长度。sizeof 的方法卸载main中可以但是对于函数的形参指针就不行了。 解决方法类模板引用。
templateclass T
void arr(T a)
{int n sizeof(a) / sizeof(a[0]);cout n endl;
}int main()
{int a[] { 6,-1,3,-4,-6,9,2,-2,5 };arr(a);
}总结其实就是确定指向pre-next ,激活当前pre pre-next总代码 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dummy new ListNode(0); 记录一下头的位置ListNode* cur dummy; 弄个哨兵变量用于遍历while (l1 ! nullptr l2 ! nullptr) {ListNode** pp (l1-val l2-val) ? l1 : l2;cur-next *pp;cur cur-next;*pp (*pp)-next;}cur-next (l1 nullptr) ? l2 : l1;ListNode* ans dummy-next;delete dummy;return ans;}2. 删除排序链表中的重复元素
// 原来的代码有错误
ListNode* deleteDuplicates(ListNode* head) { ListNode* new_head new ListNode(head-val);ListNode* h new_head;int temp head-val;head head-next;while (head ! nullptr) {if (head-val ! temp) {h-next head;h h-next;}temp head-val;head head-next;}return new_head;
}
修改了
ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* new_head new ListNode(head-val);ListNode* h new_head;int temp head-val;head head-next;while (head ! nullptr) {if (head-val ! temp) {h-next head;h h-next;temp head-val;head head-next;}else {temp head-val;head head-next;h-next head; // 这句话一定要他不是定义他是修改}}return new_head;
} 题目四、 删除链表的倒数第 N 个结点
开始的想法
必须获得链表长度后面发现不一定循环到某个的时候跳过就好 但是发现还少了一些必须要用哑结点头节点要一视同仁
下面是我的代码没用到哑结点要不断排除特殊情况。 ListNode* removeNthFromEnd(ListNode* head, int n) {int n1 0;ListNode* cur head;while (cur ! nullptr) {n1;cur cur-next;}if (n1 1) return head-next; // 啰嗦了但是必要的int k 0;cur head;if (k n1 - n -1) return head-next;while (k n1 - n -1) {k;cur cur-next;}cur-next cur-next-next;return head;}把上面的代码稍微修改加入哑结点就好。
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;}
};作者LeetCode-Solution
链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。当然双指针发可以避免获取总长度
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);ListNode* first head;ListNode* second dummy;for (int i 0; i n; i) {first first-next;}while (first) {first first-next;second second-next;}second-next second-next-next;ListNode* ans dummy-next;delete dummy;return ans;}
};作者LeetCode-Solution
链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
