刷题 - 数据结构（二）链表

1. 链表

1.1 题目：合并两个有序链表

1. 链表的建立与插入：关键在于留出头部，创建迭代指针。

    ListNode* head = new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p = 0; // 再创建一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodep = head; // 把head 里面的地址赋值给p

完整的代码

作者：小陈写不完代码
链接：https://zhuanlan.zhihu.com/p/365219765
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。#include<iostream>
#include<string>
using namespace std;
struct node
{string name;int score;node* next;
};
node* creatList(); // 创建了一个返回值为指向数据类型为node的执政,即返回的是一个地址
int main()
{node* head=creatList();
}
node* creatList()
{node* head = new node; // 通过new 创建了一个数据类型为node的数据 并把该数据的地址赋值给nodenode* p= new node; // 再创建一个数据类型为node的数据 并把该数据的地址赋值给nodep=head; // 把head 里面的地址赋值给pp->next=NULL; //这里把p指向的数据类型为node的数据里的 指针next指向了空.指针必须有对象 即指向一个地方,你不告诉它 它就乱跑 所以一般都是让它空着while (true) // 这里我选择while循环 因为里面是true 所以会一直进行 ,我们在里面使用条件判断加break跳出来{cout<<"Please enter student name: ";cin>>p->name; // 录入学生的姓名cout<<"Please enter student score: ";cin>>p->score; // 输入学生的分数if(p->score <0){break; // 如果分数小于0 跳出循环即输入结束.}node*q =new node; // 没有跳出循环 即继续输入,这时我们再创建一个这些数据类型为node的数据 并把它的地址赋值给 指针变量 q .p->next=q; // 刚刚p指针指向的数据类型为node的数据里的 指针next 指向 q ,节点p 和 节点q连起来了..q->next=NULL; // 指针q指向的数据类型为node的数据里的指针 next 指针也不能乱指,所以我们让它指向 NULLp=q; // 这里我当初就搞了很长时间.还记的嘛 p 和 q 是什么 ,它们两都是指针变量.它们里面放的是地址,而且它们里面的地址是可以给其它的指向相同数据类型的指针的,这里我们把q里面的地址 给了p 这样p里面存放的地址就是这个链表的最后一个节点的地址.如此反复我们就实现了动态输入.}return head; // 这就是为什么我们要设置head了,因为p的地址是不断变化的,而head里面的地址是不变的.而且head里面放的就是第一个节点的地址,
}

2. 依据数组创建列表的时候，需要考虑到：函数内部不好获得数组的长度。sizeof 的方法卸载main中可以，但是对于函数的形参指针就不行了。
   解决方法：类模板+引用。

template<class 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);
}

3. 总结：其实就是：确定指向（pre->next = ）,激活当前（pre = pre->next）
4. 总代码：

 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 个结点

开始的想法：

1. 必须获得链表长度；（后面发现不一定）
2. 循环到某个的时候跳过就好
   但是发现还少了一些
3. 必须要用哑结点（头节点要一视同仁）；

下面是我的代码，没用到哑结点，要不断排除特殊情况。

    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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。