各位小伙伴们大家好，你们的柳猫这次带来了最最基础的算法干货，关于链表的基础算法，相信大家都有一种了然于胸却久久不能写对的困扰，还等什么呢，跟柳猫一起来看看吧~
链表定义：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
1.链表逆序
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *next=NULL;
ListNode *new_head=NULL;
while(head){
next=head->next;
head->next=new_head;
new_head=head;
head=next;
}
return new_head;
}
};
new_head是新链表的头指针，next是为了记录下一个要反转的结点指针。
2.链表求交点
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
std::set<ListNode*> node_set;
while(headA){
node_set.insert(headA);
}
while(headB){
if(node_set.find(headB)!=node_set.end()){
return headB;
}
}
return NULL;
}
}
用stl 的set，时间复杂度nlogn，判定超时
int get_length(ListNode *head){
int len=0;
while(head){
len++;
head=head->next;
}
return len;
}
ListNode * get_same_node(int long_len,int short_len,ListNode *head){
int delta=long_len-short_len;
while(delta--){
head=head->next;
}
return head;
}
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len_A=get_length(headA);
int len_B=get_length(headB);
if(len_A>len_B){
headA=get_same_node(len_A,len_B,headA);
}else{
headB=get_same_node(len_B,len_A,headB);
}
while(headA){
if(headA==headB){
return headA;
}
headA=headA->next;
headB=headB->next;
}
return NULL;
}
};
先求出两个链表长度，然后对齐指针。时间复杂度O（n）
3.链表求环
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast=head;
ListNode *slow=head;
while(fast && fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow) return true;
}
return false;
}
};
4.划分链表
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode moreNode(0),lessNode(0);
ListNode *more=&moreNode,*less=&lessNode;
while(head){
if(head->val < x){
less->next=head;
less=head;
}else{
more->next=head;
more=head;
}
head=head->next;
}
less->next=moreNode.next;
more->next=NULL;//注意尾指针清空！！！
return lessNode.next;
}
};
利用两个头节点挂上多于x和少于x的节点，最后修改指针，注意尾指针需要清空。
5.复杂链表的复制
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(head==NULL) return NULL;
unordered_map<RandomListNode*,RandomListNode*> m;
RandomListNode headNode(0);
RandomListNode *cur=&headNode;
RandomListNode *old_cur=head;
while(old_cur){
RandomListNode *temp=new RandomListNode(old_cur->label);
cur->next=temp;
m.insert({old_cur,temp});
cur=cur->next;
old_cur=old_cur->next;
}
cur->next=NULL;
cur=headNode.next;
old_cur=head;
while(cur){
cur->random=m[old_cur->random];
cur=cur->next;
old_cur=old_cur->next;
}
return headNode.next;
}
};
old_cur为原链表的遍历指针，cur为新链表的遍历指针
6-a.2个排序链表的归并
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode head(0);
ListNode *p=&head;
while(l1 && l2){
if(l1->val <= l2->val){
p->next=l1;
l1=l1->next;
}else{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(l1==NULL) p->next=l2;
if(l2==NULL) p->next=l1;
return head.next;
}
};
6-b.k个排序链表合并
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len=lists.size();
if(len==0) return NULL;
if(len==1) return lists[0];
if(len==2) return mergeTwoLists(lists[0],lists[1]);
int mid=len/2;
vector<ListNode *> sub_list1,sub_list2;
for(int i;i<mid;i++){
sub_list1.push_back(lists[i]);
}
for(int i=mid;i<len;i++){
sub_list2.push_back(lists[i]);
}
ListNode *l1=mergeKLists(sub_list1);
ListNode *l2=mergeKLists(sub_list2);
return mergeTwoLists(l1,l2);
}
};
mergeTwoLists函数是上面的。时间复杂度O(nklogk).
7.其他算法题型：
7.1删除指定节点
class Solution {
public:
void deleteNode(ListNode* node) {
node->val=node->next->val;
node->next=node->next->next;
}
};
给定的是要删除的节点的指针，要删除该节点，由于无法获取前面节点的next，无法通过修改该next指向后面的节点。
这里将该节点的值用其后面节点的值替换，再删除后面的节点，达到等效的作用。
7.2获取中间节点
描述：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
class solution{
public:
ListNode *getMiddleNode(ListNode *head){
ListNode *fast=head;
ListNode *slow=head;
while(fast != NULL && fast->next != NULL){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
}
8.总结：
以上基础算法包括：
- 1.链表逆序
- 2.链表求交点
- 3.链表求环
- 4.链表划分
- 5.复杂链表的复制
- 6-a.2个排序链表归并
- 6-b.k个排序链表归并
- 7.1删除指定节点
- 7.2获取中间节点