数据结构——链表
根据左神数据结构学习后做的一些笔记，和在牛客网刷题做的代码笔记
·
链表
关于单链表，比较特殊，在面试中，要时刻注意时间复杂度和额外空间复杂度的问题
所以在笔试中，额外空间的应用无所谓，能做到即可，可以使用数组作为额外空间来使用
而在面试中要注意把额外空间复杂度降到最小，所以用克隆的方式来代替额外空间
这样子可以用不多的几个变量来确定关系，而位置的关系是通过克隆的位置关系来去确定的，这样的好处是让复杂度变低的同时还达到很好的效果
桶排序
基数排序：分别按照个十百为先分别排序，然后再往上排序，对于每一位都是已经排好序，虽然不用进行比较，但是花费的空间和时间 比较多
基本稳定
在排完序之后还保持着排序前的基本序列，在班级中按照成绩排，相同的排序按照学号前后
综合排序
在小样本的时候采用一种排序方式，大样本的时候采用另一种，让整体复杂度减小
哈希表
无序的，但有序表的key是有序的
增删改查的复杂度都是常数，但是这个常数可能比较大
unordermap,unordertree
快慢指针求回文
也可以申请栈，将每个数遍历后都放进栈里面去，然后依次弹出，比较
可以采用快慢指针的方式，但是将头结点的下一位做慢指针，可以解决奇数和偶数问题
随机哈希表的设置
设置一个哈希表，将每个数的next和rand都放进哈希表里，第一次遍历老链表就是放进哈希表，第二次是根据哈希表里的next和rand，设置新链表的next和rand
直接插入克隆结点在当前结点后面，这样的话就不用在哈希表里设置next了，然后在遍历的时候设置一下边界，一对对遍历，存入rand即可，克隆节点的rand就是原本节点rand的克隆节点
有环链表
可以申请哈希表额外空间，记录每个遍历后的结点，第一次重复访问到的节点就就是环的开头
**快慢指针：**一开始都在head，慢指针一次走一步，快指针一次走两步，会在环里相遇，相遇后，快指针回到head，快慢指针同时走，都走一步，最终会在环的开始节点相遇
无环链表
判断两条链表是否在同一地址，即最后节点是否相同，因为当两条单链表有相交时，相交部分一定是相同的，next指针是不会断的。
判断最后节点相同时即可判断出他们相交
让长链表先走x 步，x为二者差值，然后二者同时走，一定会在相交节点相遇
cur1 = n>0 ? head1 : head2//谁长，谁的头是head1
cur2 = cur1 == head1 ? head2 : head1 //谁短，谁的头是cur2
重定位长短
如果是相同环，则把终止节点设置为俩链表入环节点，其余按照无环链表操作，如果不同环，从loop 1开始，如果遇得到loop2，则是不同入环节点，返回谁都可以，但如果没有，则不相交
合并k 个已排序链表
思路：多个指针，有限几个变量，采用merge方法，拆分出左右两组链表，然后进行合并，大化小
- step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2n/2n/2个链表和右边n/2n/2n/2个链表。
- step 2：继续不断递归划分，直到每部分链表数为1.
- step 3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。
class Solution {
public:
ListNode *Merge2(ListNode *phead1, ListNode *phead2){
if(phead1 == NULL) return phead2;
if(phead2 == NULL) return phead1;
ListNode *head = new ListNode(0);
ListNode *cur = head;
while(phead1 && phead2){
if(phead1->val > phead2->val){
cur->next = phead2;
phead2 = phead2->next;
}
else{
cur->next = phead1;
phead1 = phead1->next;
}
cur = cur->next;
}
if(phead1) cur->next = phead1;
else cur->next = phead2;
return head->next;
}
ListNode *divideMerge(vector<ListNode *> &lists, int left, int right){
if(left > right) return NULL;
else if (left == right) return lists[left];
int mid = (left + right) / 2;
return Merge2(divideMerge(lists, left, mid), divideMerge(lists, mid+1, right));
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
return divideMerge(lists, 0, lists.size() - 1);
}
};
链表中环的入口节点
- 可以采用哈希表，放进去的节点遇到重复的第一个就是入环节点
- 快慢指针：快指针走两步，慢指针走一步，当快慢指针相遇时，快指针返回起点，快慢指针一起走，都是走一步，再次相遇的节点就是入环节点
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(pHead == NULL ) return NULL;
ListNode *slow = pHead;
ListNode *fast = pHead;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
break;
}
if(fast == NULL || fast->next == NULL)
return NULL;
fast = pHead;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
链表中倒数最后k个结点
- 两次遍历的方法，先统计总长，然后n-k次遍历找到
- 可以快慢指针，快指针先走k步，然后和慢指针一起走
class Solution {
public:
ListNode* FindKthToTail(ListNode* pHead, int k) {
// write code here
while(pHead == NULL) return NULL;
ListNode *fast = pHead;
ListNode *slow = pHead;
for(int i=0; i<k; i++){
if(fast == NULL)
return NULL;
fast = fast->next;
}
while(fast != NULL ){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
删除链表的倒数第n个结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//添加表
ListNode* res = new ListNode(-1);
res->next = head;
//当前节点
ListNode* cur = head;
//前序节点
ListNode* pre = res;
ListNode* fast = head;
//快指针先行n步
while (n--)
fast = fast->next;
while (fast != NULL) {
fast = fast->next;
pre = cur;
cur = cur->next;
}
//删除该位置的节点
pre->next = cur->next;
//返回去掉头
return res->next;
}
};
两个链表的第一个公共结点
- 循环遍历两个链表，迟早会相遇
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while(l1 != l2){
l1 = (l1==null)?pHead2:l1.next;
l2 = (l2==null)?pHead1:l2.next;
}
return l1;
}
-
额外空间的，所有都存进去，看是否有相同的
-
双指针，先走差值步，然后同时遍历，第一个相同的就是公共结点
链表相加
- 采用反转链表的方式
class Solution { public: ListNode *reverselist(ListNode *phead){ if(phead == NULL) return phead; ListNode *cur = phead; ListNode *pre = NULL; while(cur != NULL){ ListNode *temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here if(head1 == NULL) return head2; if(head2 == NULL) return head1; head1 = reverselist(head1); head2 = reverselist(head2); ListNode *res = new ListNode(-1); ListNode *head = res; int carry = 0; while(head1 != NULL || head2 != NULL || carry !=0){ int val1 = head1 == NULL ? 0:head1->val; int val2 = head2 == NULL ? 0 : head2->val; int temp = val1 + val2 + carry; carry = temp/10; temp %= 10; head->next = new ListNode(temp); head = head->next; if(head1 != NULL){ head1 = head1->next; } if(head2 != NULL){ head2 = head2->next; } } return reverselist(res->next); } };- 采用辅助空间的方式
public class Solution { public ListNode addInList (ListNode head1, ListNode head2) { // write code here if(head1 == null) return head2; if(head2 == null){ return head1; } // 使用两个辅助栈，利用栈先进后出，相当于反转了链表 Stack<ListNode> stack1 = new Stack<>(); Stack<ListNode> stack2 = new Stack<>(); ListNode p1=head1; ListNode p2=head2; // 将两个链表的结点入栈 while(p1!=null){ stack1.push(p1); p1=p1.next; } while(p2!=null){ stack2.push(p2); p2=p2.next; } // 进位 int tmp = 0; // 创建新的链表头节点 ListNode head = new ListNode(-1); ListNode nHead = head.next; while(!stack1.isEmpty()||!stack2.isEmpty()){ // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值） int val = tmp; // 栈1不为空的时候，弹出结点并累加值 if (!stack1.isEmpty()) { val += stack1.pop().val; } // 栈2不为空的时候，弹出结点并累加值 if (!stack2.isEmpty()) { val += stack2.pop().val; } // 求出进位 tmp = val/10; // 进位后剩下的数值即为当前节点的数值 ListNode node = new ListNode(val%10); // 将结点插在头部 node.next = nHead; nHead = node; } if(tmp > 0){ // 头插 ListNode node = new ListNode(tmp); node.next = nHead; nHead = node; } return nHead; } }
单链表的排序
- 数组形式：创建一个数组，将链表内容放入，然后排序完恢复链表形式
class Solution { public: ListNode* sortInList(ListNode* head) { vector<int> nums; ListNode* p = head; //遍历链表，将节点值加入数组 while(p != NULL){ nums.push_back(p->val); p = p->next; } p = head; //对数组元素排序 sort(nums.begin(), nums.end()); //遍历数组 for(int i = 0; i < nums.size(); i++){ //将数组元素依次加入链表 p->val = nums[i]; p = p->next; } return head; } };- 递归形式：每次分成两部分，然后将分割后的部分进行局部排序，最终达到整体有序
class Solution { public: ListNode *mergelist(ListNode *phead1, ListNode *phead2){ if(phead1 == NULL) return phead2; if(phead2 == NULL ) return phead1; ListNode *head = new ListNode(0); ListNode *cur = head; while(phead1 && phead2){ if(phead1->val >phead2->val){ cur->next = phead2; phead2 = phead2->next; }else{ cur->next = phead1; phead1 = phead1->next; } cur = cur->next; } if(phead1) cur->next = phead1; else cur->next = phead2; return head->next; } ListNode* sortInList(ListNode* head) { // write code here if(head == NULL || head->next == NULL) return head; ListNode *left = head; ListNode *mid = head->next; ListNode *right = head->next->next; while(right != NULL && right->next != NULL){ left = left->next; mid = mid->next; right = right->next->next; } //左边指针指向左段的左右一个节点，从这里断开 left->next = NULL; //分成两段排序，合并排好序的两段 return mergelist(sortInList(head), sortInList(mid)); } };
判断链表是否为回文结构
-
存入数组的方式，然后将数组反转后对比
-
存入数组的方式，得到数组长度，双指针分别从两端开始
class Solution { public: bool isPail(ListNode* head) { vector<int> nums; //将链表元素取出一次放入数组 while(head != NULL){ nums.push_back(head->val); head = head->next; } //双指针指向首尾 int left = 0; int right = nums.size() - 1; //分别从首尾遍历，代表正序和逆序 while(left <= right){ //如果不一致就是不为回文 if(nums[left] != nums[right]) return false; left++; right--; } return true; } };- 快慢指针方式，记录到中间位置，然后反转后半部分，再对比（满足时间O(n)，空间O(1)）
class Solution { public: ListNode *reverse(ListNode *head){ ListNode *pre = NULL; while(head != NULL){ ListNode *next = head->next; head->next = pre; pre = head; head = next; } return pre; } bool isPail(ListNode* head) { // write code here ListNode *slow = head->next; ListNode *fast = head; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; } fast = head; slow = reverse(slow); while(slow != NULL){ if(fast->val != slow->val) return false; slow = slow->next; fast = fast->next; } return true; } };
链表的奇偶重排
- 双指针的方式，将偶数的节点跳过，奇数的next直接指向下一个奇数，偶数则成为奇数的next
class Solution { public: ListNode* oddEvenList(ListNode* head) { // write code here if(head == NULL) return NULL; ListNode *even = head->next; ListNode *odd = head; ListNode *evenodd = even; while(even != NULL && even->next != NULL){ odd->next = even->next; odd = odd->next; even->next = odd->next; even = even->next; } odd->next = evenodd; return head; } };
删除有序链表中重复的所有元素
- 从0开始，不从1开始，这样的话可以从重复节点的上一个开始判断，每一次遇到重复前都可以判断出后面两个是否有重复元素
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { // write code here if(head == NULL) return NULL; ListNode *res = new ListNode(0); res->next = head; ListNode *cur = res; while(cur->next != NULL && cur->next->next != NULL) { if(cur->next->val == cur->next->next->val){ int temp = cur->next->val; while(cur->next != NULL && cur->next->val == temp){ cur->next = cur->next->next; } }else cur = cur->next; } return res->next; } };
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)