链表专题

贪心算法

有1元、2元、5、10、20、50、100元的钞票无穷多张，现支付x元，最少需要多少张？

#include <iostream>
#include <vector>
using namespace std;
vector<int> a{100,50,20,10,5,2,1};
int main(){
    int x,num;
    cin >>  x;
    for(int i=0;i<a.size();i++){
        int b =x/a[i];//需要几张
        cout << "need " << a[i] << " " << b << endl;
        num +=b;
        x -=b*a[i];
    }
    return 0;
}

链表

创建一个链表并打印

//创建链表
struct ListNode {
    int val;//数据域
    ListNode* next;//指针域

};
int main(){
    //创建链表
    ListNode a,b,c,d,e;
    a.next =&b;
    b.next = &c;
    c.next =&d;
    d.next =&e;
    e.next = NULL;
    //赋值
    ListNode *p = &a;
    int i=1;
    while(p){
        p->val = i;
        i++;
        p = p->next ;
    }
    //打印
    p = &a;
    while (p){
        cout << p->val << " ";
        p = p->next ;
    }
    return 0;
}

反转链表

注意点

• 是否从第一个开始，涉及到第一个节点有没有置换位置
• 判断交换部分的尾节点的下一个节点是否为空

#include <iostream>
using namespace std;
//创建链表
typedef struct  ListNode {
    int val;//数据域
    ListNode* next;//指针域
    //ListNode();
    //ListNode(int a) :val(a),next(NULL){}
}ListNode ,*Lise;
ListNode * reverseList(ListNode *head){
        if(head== NULL || head ->next == NULL) return head; //如果为空，则返回
        ListNode *p =head;
        ListNode *q = head ->next;

        while(q){
            ListNode * tmp =q->next;
            q->next = p;
            p=q;
            q =tmp;
    }
        head->next =NULL;
        return p;
}
int main(){
    //创建链表
    ListNode a,b,c,d,e;
    a.next =&b;
    b.next = &c;
    c.next =&d;
    d.next =&e;
    e.next = NULL;
    //赋值
    ListNode *p = &a;
    int i=1;
    while(p){
        p->val = i;
        i++;
        p = p->next ;
    } 
    //打印
    p = reverseList(&a);
  //  p = &a;
    while (p){
        cout << p->val << " ";
        p = p->next ;
    }
    return 0;
}

区间反转链表

#include <iostream>
using namespace std;
//创建链表
typedef struct  ListNode {
    int val;//数据域
    ListNode* next;//指针域
    //ListNode();
    //ListNode(int a) :val(a),next(NULL){}
}ListNode ,*List;
ListNode * reverseList(ListNode *head){
        if(head== NULL || head ->next == NULL) return head; //如果为空，则返回
        ListNode *p =head;
        ListNode *q = head ->next;
        while(q){
            ListNode * tmp =q->next;
            q->next = p;
            p=q;
            q =tmp;
    }
        head->next =NULL;
        return p;
}
ListNode *reverseListRange(ListNode *head,int start,int end){
    int len = end -start;
    ListNode *result =head;
    //先到头节点,并记录前节点
    ListNode *pre_head = head;
    int m =start;
    while(--start){ // 往前移动 m-1 个位置
        pre_head = head;
        head = head->next;
    }
    ListNode *p =head;
    ListNode *q =head->next;
    while(q&&len){
        len--;
        ListNode *tmp = q->next;
        q->next = p;
        p=q;
        q=tmp;
    }
    if(m==1){
        q? pre_head->next = q:pre_head->next=NULL;
        result = p;
    }
    else{
        if(q!=NULL){
            pre_head->next->next = q;
        }
        else pre_head->next->next =NULL;
        pre_head->next = p;
    }
    return result;
}
int main(){
    //创建链表
    ListNode a,b,c,d,e;
    a.next =&b;
    b.next = &c;
    c.next =&d;
    d.next =&e;
    e.next = NULL;
    //赋值
    ListNode *p = &a;
    int i=1;
    while(p){
        p->val = i;
        i++;
        p = p->next ;
    }
    //打印
  //  p = reverseList(&a);
   p = reverseListRange(&a,1,4);
   //p = &a;
    while (p){
        cout << p->val << " ";
        p = p->next ;
    }
    return 0;
}

求链表的交点

1. 使用 set 地址是否相同

#include <iostream>
#include <set>
using namespace std;
typedef  struct ListNode{
    int val;
    ListNode *next;
    //初始化
    ListNode(int a):val(a),next(NULL){}
}ListNode,*List;

class solution{
public:
    ListNode* getIntersectionNode(ListNode* headA,ListNode* headB){
        set<ListNode*> sNode;
        while(headA){
            sNode.insert(headA);
            headA = headA->next;
        }
        while(headB){
            if((sNode.find(headB))!=sNode.end() ){// 返回一个迭代器，不是指向尾节点
                return headB;
            }
            headB = headB->next;
        }
        return NULL;
    }
};
void Print(ListNode *head){
   while(head){
       cout << head->val <<" ";
       head=head->next;
   }
}
int main(){
    ListNode a1(1),a2(2);
    ListNode b1(3),b2(4),b3(5);
    ListNode c1(6),c2(7),c3(8);

    a1.next = &a2;
    a2.next =&c1;
    b1.next = &b2;
    b2.next=&b3;
    b3.next = &c1;
    c1.next = &c2;
    c2.next = &c3;
    c3.next =NULL;
    Print(&a1);
    cout<<endl;
    Print(&b1);
    cout << endl;

    solution s;
    ListNode* p = s.getIntersectionNode(&a1,&b1);
    cout << p->val << endl;
    return 0;
}

1. 求长度再对齐

#include <iostream>
#include <set>
using namespace std;
typedef  struct ListNode{
    int val;
    ListNode *next;
    //初始化
    ListNode(int a):val(a),next(NULL){}
}ListNode,*List;
namespace s1{
    class solution{
    public:
        ListNode* getIntersectionNode(ListNode* headA,ListNode* headB){
            set<ListNode*> sNode;
            while(headA){
                sNode.insert(headA);
                headA = headA->next;
            }
            while(headB){
                if((sNode.find(headB))!=sNode.end() ){// 返回一个迭代器，不是指向尾节点
                    return headB;
                }
                headB = headB->next;
            }
            return NULL;
        }
    };
}

namespace  s2{
    // 计算链表长度
    int lengthList(ListNode* pL){
        int len=0;
        while(pL){
            len++;
            pL = pL->next;
        }
        return len;
    }

        ListNode* move_longList(int long_length,int short_length,ListNode* head){
            int d = long_length -short_length;
            while(head&&d){
                d--;
                head= head->next;
            }
            return head;
    }
    class solution2{
    public:
        ListNode *getIntersectionNode(ListNode* headA,ListNode* headB){
            int lenA = lengthList(headA);
            int lenB = lengthList(headB);
            if(lenA>=lenB){
                //指针前移
                headA = (lenA,lenB,headA);
            } else{
               headB =  move_longList(lenB,lenA,headB);
            }
            while (headA&&headB){
                if(headA==headB) return  headA;
                headA = headA->next;
                headB = headB->next;
            }
            return NULL;
        }
    };
}

void Print(ListNode *head){
   while(head){
       cout << head->val <<" ";
       head=head->next;
   }
}
int main(){
    ListNode a1(1),a2(2);
    ListNode b1(3),b2(4),b3(5);
    ListNode c1(6),c2(7),c3(8);

    a1.next = &a2;
    a2.next =&c1;
    b1.next = &b2;
    b2.next=&b3;
    b3.next = &c1;
    c1.next = &c2;
    c2.next = &c3;
    c3.next =NULL;
    Print(&a1);
    cout<<endl;
    Print(&b1);
    cout << endl;

    s1::solution s;
    ListNode* p = s.getIntersectionNode(&a1,&b1);
    cout << p->val << endl;

    s2::solution2 ms2;
    p = ms2.getIntersectionNode(&a1,&b1);
    cout << p->val << endl;

    return 0;
}

检测链表有环

1. set实现

// set实现
#include <iostream>
#include <set>
using namespace std;
typedef  struct ListNode{
    int val;
    ListNode *next;
    //初始化
    ListNode(int a):val(a),next(NULL){}
}ListNode,*List;
void Print(ListNode *head){
    while(head){
        cout << head->val <<" ";
        head=head->next;
    }
}
// 用set
namespace s1{
    class solution{
    public:
        ListNode* dectecircle(ListNode *head){
            set<ListNode*> sNode;
            while(head){
                if(sNode.find(head)!=sNode.end()){
                    return head;
                }
                sNode.insert(head);
                head = head->next;
            }
            return NULL;
        }
    };
}

int main(){
    ListNode a(1),b(2),c(3),d(4),e(5),f(6),g(7);
    a.next =&b;
    b.next=&c;
    c.next=&d;
    d.next=&e;
    e.next=&f;
    f.next=&g;
    g.next=&c;

    s1::solution ms1;
    ListNode* p=ms1.dectecircle(&a);
    cout << p->val << endl;
    //Print(&a);
    return 0;
}

1. 快慢指针实现

//
// Created by er on 2020/5/24.
//链表求环
//

#include <iostream>
#include <set>
using namespace std;
typedef  struct ListNode{
    int val;
    ListNode *next;
    //初始化
    ListNode(int a):val(a),next(NULL){}
}ListNode,*List;
void Print(ListNode *head){
    while(head){
        cout << head->val <<" ";
        head=head->next;
    }
}
// 用set
namespace s1{
    class solution{
    public:
        ListNode* dectecircle(ListNode *head){
            set<ListNode*> sNode;
            while(head){
                if(sNode.find(head)!=sNode.end()){
                    return head;
                }
                sNode.insert(head);
                head = head->next;
            }
            return NULL;
        }
    };
}
namespace  s2{
    class solution{
    public:
        ListNode* dectecircle(ListNode *head){
            ListNode *fast = head;
            ListNode *slow = head;
            while (fast){
                slow=slow->next;
                fast=fast->next;
                if(fast==NULL){
                    return NULL;
                }
                fast=fast->next;

                if(fast==slow)
                    break;
            }
            while(head && slow){
                if(slow ==head )
                    return head;
                head=head->next;
                slow = slow->next;
            }
        }
    };
}

int main(){
    ListNode a(1),b(2),c(3),d(4),e(5),f(6),g(7);
    a.next =&b;
    b.next=&c;
    c.next=&d;
    d.next=&e;
    e.next=&f;
    f.next=&g;
    g.next=NULL;

    s1::solution ms1;
    ListNode* p=ms1.dectecircle(&a);
    if(!p) cout << "NULL" <<endl;
    else cout << p->val << endl;

    s2::solution ms2;
     ListNode *p1 = ms2.dectecircle(&a);
     if(!p1) cout << "null" <<endl;
    else cout << p1->val << endl;

    //Print(&a);
    return 0;
}

链表的归并排序

1. 链表的划分

#include <iostream>
#include <set>
using namespace std;
typedef  struct ListNode{
    int val;
    ListNode *next;
    //初始化
    ListNode(int a):val(a),next(NULL){}
}ListNode,*List;
void Print(ListNode *head){
    while(head){
        cout << head->val <<" ";
        head=head->next;
    }
}

class solution{
public:
    ListNode* parition(ListNode* head,const int x){
        //定义两个头节点
        ListNode leftNode(-1),rightNode(-1);
        ListNode* lowptr = &leftNode;
        ListNode* moreptr = &rightNode;


        while(head){
            if(head ->val < x){
                lowptr->next = head;
                lowptr =head;
            } else{
                moreptr->next  =head;
                moreptr = head;
            }
            head=head->next;
        }

        lowptr->next = rightNode.next;
        moreptr->next =NULL;
        return leftNode.next;
    }
};

int main(){

    ListNode a(1),b(9),c(6),d(4),e(5),f(6),g(1);
    a.next =&b;
    b.next=&c;
    c.next=&d;
    d.next=&e;
    e.next=&f;
    f.next=&g;
    g.next=NULL;
    Print(&a);

    cout << endl;
    solution s;
    ListNode *p = s.parition(&a,7);
    Print(p);
    return 0;
}

复杂链表的深度拷贝

leetcode 138

//
// Created by er on 2020/5/26.
//
//复杂的链表的深度拷贝

#include <iostream>
#include <map>
#include <vector>
using namespace std;
//数据结构
struct RandomListNode{
    int num;
    RandomListNode *next;
    RandomListNode *random;
    RandomListNode(int x):num(x),next(NULL),random(NULL){}
};
//解决方法
class solution{
public:
    RandomListNode *copyRandomList(RandomListNode *head){
        RandomListNode *p =head;
        vector<RandomListNode*> vListAddress;//保存节点地址
        map<RandomListNode*,int> mListNodeRandom; //关键语句 ，将每个地址映射为 数字0、1、2、3. ...

        //开辟新的节点
        int i =0;
        while(p){
            vListAddress.push_back(new RandomListNode(p->num ));
            mListNodeRandom[p]= i;
            i++;
            p = p->next;
        }
            //next random 赋值
            p =head;
            i=0;
            vListAddress.push_back(0);
            while(p){
                vListAddress[i]->next = vListAddress[i+1];
                if(p->random) //这句判断很重要，因为如果为空的话，就会映射到0 的位置，产生错误结果。
                vListAddress[i]->random = vListAddress[mListNodeRandom[p->random]]; // 关键语句
                i++;
            p=p->next;
        }
        return vListAddress[0];
    }

};
int main(){
    RandomListNode a(1),b(2),c(3),d(4),e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    a.random = &c;
    b.random = &d;
    c.random = &c;
    d.random = NULL;
    e.random = &d;

    solution s;
    RandomListNode *r = s.copyRandomList(&a);

    while(r){
        if(r->random) cout << r->random->num << " ";
        else cout << "NULL" << " ";
        r=r->next;
    }
    return 0;
}

2个有序链表的合并

//
// Created by er on 2020/5/26.
//排序链表的合并
//leetcode 21
//
// 归并排序，双指针算法
#include <iostream>
using namespace std;
struct ListNode{
    int num;
    ListNode* next;
    ListNode(int x):num(x),next(NULL){}
};
class solution{
public:
    ListNode* MergeSortedList(ListNode* head1,ListNode* head2){
        ListNode tempHead(0);
        ListNode *p =&tempHead;

        while(head1&&head2){
            if(head1->num <= head2->num) {
                p->next = head1;
                head1=head1->next;
            } else{
                p->next = head2;
                head2 = head2->next;
            }
            p =p->next;
        }
        if(head1) p->next = head1;
        if(head2) p->next =head2;
        return tempHead.next;
    }
};
int main(){
    ListNode a(1),b(4),c(6),d(0),e(5),f(7);
    a.next = &b;
    b.next = &c;
    d.next = &e;
    e.next = &f;

    solution s;
    ListNode *p = s.MergeSortedList(&a,&d);
    while (p){
        cout << p->num << " ";
        p=p->next;
    }
    return 0;
}

多个有序链表的合并

• 使用vector 排序实现 时间复杂度 O(KNlogKN)
• 使用分治思想 时间复杂度 O(KNlogK)

//
// Created by er on 2020/5/26.
//k个有序链表合并
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode{
    int num;
    ListNode* next;
    ListNode(int x):num(x),next(NULL){}
};
bool cmp(ListNode* l1,ListNode* l2){
    return l1->num < l2->num;
}
// 将所有节点放入到vector中，排序重新连接
namespace s1{
    class solution{
    public:
        ListNode* MergeKSortedList(vector<ListNode*> vList){
            vector<ListNode*> vListnode;
            if(vList.empty()) return NULL;
            for(int i=0;i<vList.size();i++){
                ListNode* head = vList[i];
                while (head){
                    vListnode.push_back(head);
                    head=head->next;
                }
            }
            sort(vListnode.begin()  ,vListnode.end(),cmp);
            for(int i=1;i<vListnode.size();i++){
                vListnode[i-1]->next = vListnode[i];
            }
            vListnode[vListnode.size()-1]->next =NULL;
            return vListnode[0];
        }
    };
}

//利用分治的思想
namespace s2{
    class solution{
    public:
        ListNode* MergeSortedList(ListNode* head1,ListNode* head2){
            ListNode tempHead(0);
            ListNode *p =&tempHead;

            while(head1&&head2){
                if(head1->num <= head2->num) {
                    p->next = head1;
                    head1=head1->next;
                } else{
                    p->next = head2;
                    head2 = head2->next;
                }
                p =p->next;
            }
            if(head1) p->next = head1;
            if(head2) p->next =head2;
            return tempHead.next;
        }
        ListNode* MergeKSortedList(vector<ListNode*> vList){
            if(vList.size()==0) return NULL;
            if(vList.size()==1) return vList[0];
            if(vList.size()==2) return MergeSortedList(vList[0],vList[1]);

            int mid = vList.size()/2;
            // 划分为不同的区间
            vector<ListNode*> vSubList1,vSubList2;
            for(int i=0;i<mid;i++){
                vSubList1.push_back(vList[i]);
            }
            for(int i=mid;i<vList.size();i++){
                vSubList2.push_back(vList[i]);
            }
           ListNode*l1 =  MergeKSortedList(vSubList1);
           ListNode*l2 =  MergeKSortedList(vSubList2);
            return MergeSortedList(l1,l2);
        }
    };
}

void Print(ListNode* head){
    if(head==NULL) cout << "NULL" ;
    while(head){
     cout << head->num << " ";
     head=head->next;
    }
}
int main(){
    ListNode a(1),b(4),c(6),d(0),e(5),f(7),g(2),h(3);
    a.next = &b;
    b.next = &c;

    d.next = &e;
    e.next = &f;

    g.next =&h;

    s1::solution ms1;
    vector<ListNode* >  vList;
    vList.push_back(&a);
    vList.push_back(&d);
    vList.push_back(&g);
    ListNode *head1 = ms1.MergeKSortedList(vList);
    Print(head1);
    cout << endl;
    cout << "------------" << endl;
//方法二
//    s2::solution ms2;
//    vector<ListNode* >  vList1;
//    vList1.push_back(&a);
//    vList1.push_back(&d);
//    vList1.push_back(&g);
//    ListNode *head2 = ms2.MergeKSortedList(vList1);
//    Print(head2);
//    cout << endl;

    return 0;
}