剑指offer之链表

一、杂话：数据结构的储存方法无非两种，一种用数组，顺序存储，一种用链表，称为链式存储。数组和链表都属于线性结构，是其余数据结构的基础。因此，在讲完数组之后，自然就是链表了。
二、链表的相关知识点
①我所认识的链表：我的理解中，链表就是用一条绳子将一个个数据串在一起，但是只能顺着串，不能反过来。
②注意细节：
1.在链表中要区分链表指针和链表结点，链表指针是指向链表的地址，而结点具有数据和链表指针。
创建头结点时，用的new其实是分配了一个链表的大小，可以认为这个空间其实就是头结点，但是我们用的是这个指向头结点的头指针。形如:ListNode<int>* p=new ListNode<int>();实际上是创建了一个指向头结点空间的头指针p。
2.另外，在c中承认NULL等效于nullptr，但是在c++中有所区分，所以用到指针的话，得用nullptr。
3.创建链表时，注意必要的判空语句，不要对空指针应用。
如：if(tmp!=nullptr&&tmp->next!=nullptr) ListNode<int> *p=tmp->next;
4.结构体内可以有指向该结构体类型的指针，但不可以含该类型的成员。
5.xx类型的指针就可以使用xx类的成员。如：int *p=new int[10],则p[0]是允许的。
又如：ListNode<int> *p=new ListNode<int>(),则p->next也是允许的。所以就可以理解为啥head->next了
③链表的结构定义：</int></int></int></int></int>

template <typename T>
struct ListNode{//也可用class定义
    T val;//刷题时不难发现多数T=int
    struct ListNode *next;//struct写不写都可
    ListNode():val(0),next(nullptr){};
    ListNode(T n):val(n),next(nuulptr){};
};

创建链表：

ListNode<int>* head = new ListNode<int>();
    //由向量建立一个链表
    vector<int>v{ 1,2,3,4,5,6,7 };
    ListNode<int>* tmp = head;//对临时链表操作,注意不能删除，否则会删除相应的空间，导致掉链
    for (int i = 0; i < v.size(); ++i) {
        tmp->next = new ListNode<int>(v[i]);
        tmp=tmp->next;
    }
    //打印链表
    tmp = head->next;
    while (tmp != nullptr) {
        cout << tmp->val << "->";
        tmp = tmp->next;
    }
    cout << endl;

④链表的常见操作
因为来链表分为单向链表，静态链表，循环链表和双向链表，静态链表使用二维数组来实现储存的，过程复杂而不常用，不做讨论。仅讨论其余三种链表的常见操作。
1.单向链表的常见操作：
为了让链表的插入和删除操作都一致，会在单项链表中引入一个头结点head。让其指向存有数据的第一个结点。
(1)插入操作

//插入操作
    //比如插入num=8到位置pos=3
    int num = 8; int pos = 3;
    tmp = head;//对临时链表操作
    while ((--pos)&&tmp!=nullptr){
        tmp = tmp->next; 
    }
    if (tmp != nullptr) {
        ListNode<int>* tmplist = tmp->next;//使用临时链表保持信息,注意不能删除，否则会删除相应的空间，导致掉链
        tmp->next = new ListNode<int>(num);
        tmp->next->next = tmplist;  
    }
    //打印链表
    tmp = head->next;
    while (tmp != nullptr) {
        cout << tmp->val << "->";
        tmp = tmp->next;
    }
    cout << endl;

注意一点就是：中间新建的临时指针，不要删除掉，否则对应的链可能会因此断掉，这个删除结点时是不同。
（2）删除操作

    //比如删除pos=2的元素
    int pos = 2;
    tmp = head;
    while ((--pos) && tmp !=nullptr) {
        tmp = tmp->next;
    }
    if (tmp!=NULL&&tmp->next != nullptr) {
        ListNode<int>* p = tmp->next;
        tmp->next = p->next;
        free(p);//删除不要的结点，释放空间
    }
    //打印链表
    tmp = head->next;
    while (tmp != nullptr) {
        cout << tmp->val << "->";
        tmp = tmp->next;
    }
    cout << endl;

2.循环链表
循环链表需要让最后结点指向头结点，并创建一个尾指针，指向最后结点，而头结点原先是由头指针指向的，因此只需把头指针赋值给尾指针即可。
(1)插入操作：

//循环链表的额外动作
    tmp->next = head;//最后结点指向头结点
    //制造尾指针
    ListNode<int>* rear = tmp;
    //打印链表
    tmp = head; int recycle = 16;//控制打印次数
    while ((recycle--)&&tmp != NULL) {
        cout << tmp->val << "->";
        tmp = tmp->next;
    }
    cout << endl;

    //插入操作
    //比如在位置pos=1处插入num=99;
    //循环链表一般情况只给了尾指针，因此不知道头结点在哪，所以只能从尾指针查找
    int pos = 1; int num = 99;
    while ((pos--) && rear != nullptr) {
        rear = rear->next;
    }
    if (rear != nullptr&&rear->next!=nullptr) {
        ListNode<int>* p = rear->next;
        rear->next = new ListNode<int>(num);
        rear->next->next = p;
    }
    //再次打印
    tmp = head;  recycle = 16;//控制打印次数
    while ((recycle--) && tmp != nullptr) {
        cout << tmp->val << "->";
        tmp = tmp->next;
    }
    cout << endl;

(2)删除操作

    //删除操作
    //比如删除在位置pos=3的数
    int pos = 3;
    while ((pos--) && rear != nullptr) {
        rear = rear->next;
    }
    if (rear != nullptr && rear->next != nullptr) {
        ListNode<int> *tmplist = rear->next;
        rear->next = tmplist->next;
        free(tmplist);
    }

3.双向链表
由于双向链表比单链表多了一个指向前一个链表的指针，所以得重新定义它的结构：

template <typename T>
struct DListNode {
    T val;
    struct DListNode* front;
    struct DListNode* next;
    DListNode() :val(0),front(nullptr), next(nullptr) {};
    DListNode(T n) :val(n), front(nullptr), next(nullptr) {};
};

    //由向量建立链表
    DListNode<int>* dhead = new DListNode<int>();//头结点头指针
    DListNode<int>* dtmp = dhead;//临时操作指针
    vector<int>v{ 1,2,3,4,5,6,7 };
    for (int i = 0; i < v.size(); ++i) {
        DListNode<int> * newlist= new DListNode<int>(v[i]);
        dtmp->next = newlist;
        newlist->front = dtmp;
        dtmp = dtmp->next;
    }
    DListNode<int>* dtail = new DListNode<int>();//尾结点尾指针
    dtmp->next = dtail;//最后结点指向尾结点
    dtail->front = dtmp;//注意尾结点的前指针要指向最后一个结点

    //顺着打印
    cout << "顺着打印：" << endl;
    dtmp = dhead;
    while (dtmp != nullptr) {
        cout << dtmp->val << "->";
        dtmp = dtmp->next;

    }
    cout << endl;
    //逆着打印
    cout << "逆着打印\n";
    dtmp = dtail;
    while (dtmp != nullptr) {
        cout << dtmp->val << "->";
        dtmp = dtmp->front;

    }

(1)插入操作
由于双向链表多了一个指向前面的指针，因此插入和删除时会与单链表有点不同。

    //插入结点
    //比如在位置pos=4，插入num=100
    dtmp = dhead;
    int pos = 4; int num = 100;
    while ((--pos) && dtmp != nullptr) {
        dtmp = dtmp->next;
    }
    if (dtmp != nullptr && dtmp->next != nullptr) {
        DListNode<int>* newdlist = new DListNode<int>(num);
        DListNode<int>* p = dtmp->next;
        newdlist->next = p;
        p->front = newdlist;
        dtmp->next = newdlist;
        newdlist->front = dtmp;//需要四步建立四个指针
    }

(2)删除操作

   //删除结点
    //比如删除位置pos=5的结点
    dtmp = dhead;
    int pos = 5;
    while ((--pos)&&dtmp!=nullptr) {
        dtmp = dtmp->next;
    }
    if (dtmp != nullptr && dtmp->next != nullptr) {
        DListNode<int>* q = dtmp->next;
        dtmp->next = q->next;
        q->next->front = dtmp;
        free(q);

    }

⑤链表的用途:
链表的大小是可变的，不需要像数组一样提前给定长度，而且插入和删除操作比数组简单，所以具有一定的灵活性，但是寻找对应下标时，就没数组这么方便了。所以如果只需要存储，不太需要查找的话，用链表时比较合适的。
三、刷题总结
①JZ3 从尾到头打印链表---较难

思路：直接看代码吧。也就三种。方式一和方式二其实是一致的。方式三涉及到链表反转，之后的题会用到。

    vector<int> printListFromTailToHead(ListNode* head) {
        /*法一：用reverse*/
        /*vector<int>ArrayList;
        while(head!=nullptr){
            ArrayList.push_back(head->val);
            head=head->next;
        }
        reverse(ArrayList.begin(), ArrayList.end());
        return ArrayList;*/
        /*法二：用栈*/
        /*stack<ListNode*>s;vector<int>ArrayList;
        while(head!=nullptr){
            s.push(head);
            head=head->next;
        }
        while(!s.empty()){
            ArrayList.push_back(s.top()->val);
            s.pop();
        }
        return ArrayList;*/
        /*方法三：反转链表*/
        vector<int>res;
        ListNode*pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr){
            ListNode *tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        while(pre!=nullptr){
            res.push_back(pre->val);
            pre=pre->next;
        }
        return res;
    }

②JZ 链表中倒数第k个结点---中等

思路:这个题其实很简单，只要统计出结点的个数n，然后倒数第k个实际就是正数n-k个。

ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        //简单解法：既然要求倒数第k个结点，问题等效于求第n-k+1个结点
        int sum=0;ListNode *p=pHead;
        //统计结点总数
        while(p!=nullptr){
            sum++;
            p=p->next;
        }
        if(k>sum) return nullptr;
        for(int i=0;i<sum-k;i++) pHead=pHead->next;
        return pHead;
    }

分析下下：当然这样的时间复杂度是O(n),空间复杂度是O(1)。当然也可以把链表元素放到数组中，这样其实也一样，不过对于取出多个元素时，这种方法就会方便很多。
③JZ15 反转链表---中等

思路：
方法一：用栈 ，但是要注意就是必须重新创造新的结点，然后把原结点的值赋给新的结点，不断创造新结点，连接结点，同时还要删除旧结点。显然空间复杂度和时间复杂度都为O(n)。
代码如下：

    ListNode* ReverseList(ListNode* pHead) {
        //利用栈来实现反转
        if(pHead==NULL||pHead->next==NULL)    return pHead;
        stack<ListNode *> s;ListNode *reverseList;
        while(pHead!=NULL){
            s.push(pHead);
            pHead=pHead->next;
        }
        reverseList = new ListNode(s.top()->val); free(s.top()); s.pop();
        pHead = reverseList;
        while (!s.empty()) {
            pHead->next = new ListNode(s.top()->val); free(s.top()); s.pop();
            pHead = pHead->next;
        }
        return reverseList;
}

方法二：前面的题目已经有涉及到了。其实就是交换指针就行了。
具体方法见图：

初始化pre=nullptr，cur=head,然后，每次先存下tmp=cur->next,修改cur->next=pre,再移动pre=cur,cur=tmp。重复上述动作，直至当前的cur==nullptr，此时的pre就是新的链表的第一个结点。
代码如下：

ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL||pHead->next==NULL)    return pHead;
        ListNode *pre=NULL,* cur=pHead;
        while(cur!=NULL){
            ListNode *temp=cur->next;
            cur->next=pre;//反指向
            pre=cur;
            cur=temp;
        }
        return pre;
}

显然，指针改变指针，时间复杂度为O(n)，但空间复杂度为O(1)。比方法一要好。
//////////////////////////////////////////////////////////////////////////////////
特别的，k个一组反转链表
/////////////////////////////////////////////////////////////////////////////////

//1.反转链表中的一段，通用的函数
//返回新首节点
ListNode * reverse(ListNode *head,ListNode *tail){
    ListNode *pre=nullptr,* next=nullptr;
    //为了维护原首节点，即现段末节点，用tmp做临时操作
    ListNode * tmp=head;
    while(head!=tail){
        next=tmp->next;
        tmp->next=pre;
        pre=tmp;tmp=next;
    }
    return pre;
}

//2. 实现k个一组递归反转
ListNode *reverseKGroup(ListNode *head,int k){
    //recursion
    //base case 
    if(!head||!head->next)    return head;
    //operations
    //先找到tail,tail是下一段反转的起始节点
    ListNode *tail=head;
    for(int i=0;i<k;++i){
        if(!tail)    return head;//不够k个，无需反转
        tail=tail->next;
    }
    //获取新链表的节点
    ListNode *newhead=reverse(head,tail,k);
    //原首节点是现在反转段的末节点,往下连接tail开始新的反转段
    head->next=reverseKGroup(tail,k);
    return newhead;
}

④JZ16 合并两个排序的链表---简单

思路：大致归为两种解法，一种是创造新的链表，比较两链表的结点，然后往新链表中按顺序放入结点。另一种是直接递归，可以理解为，要么下一个结点是在链1，要么在链2，不断递推下去，最终会有一个链空了，这时就是回归的时候。

//创造新的链表
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    ListNode *res=new ListNode(-1);//头结点头指针
    while(pHead1&&pHead2){
        if(pHead1->val>pHead2->val){
            res->next=pHead1;
            pHead1=pHead1->next;
        }
        else{
            res->next=pHead2;
            pHead2=pHead2->next;  
        }
        res=res->next;

    }
    res->next= pHead1? pHead1:pHead2;
    return res->next;
}

//递归解法
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    if(pHead1==nullptr)    return pHead2;
    else if(pHead2==nullptr)    return pHead1;
    else if(pHead1->val<pHead2->val){
        pHead1->next=Merge(pHead1->next,pHead2);
        return pHead1;
    }
    else{
        pHead2->next=Merge(pHead1,pHead2->next);
        return pHead2;
    }
}

思考：递归看着好像很玄学，原因在于并不清楚，怎么递推，怎么回归。是否可以理解为，问题由很多子问题组成，而子问题与问题一致，所以有点像俄罗斯套娃，因此递归？以后明白了，再回来解答这个困惑吧。
⑤JZ25 复杂链表的复制---较难

1.解题前，先理解下何为浅拷贝，何为深拷贝：
所谓浅拷贝，其实就是拷贝的时候，指向的内存是同一个地方，改变这个新的对象，也会改变原对象的内容，可以理解为就是拷了一个指针，指向了原对象的地址。浅拷贝主要出现在类里面，当定义了一个对象之后，再定义一个新对象，并直接将第一个对象赋值给新对象时，如果没有自定义拷贝函数，就会调用默认的拷贝函数，这时，新对象的内容，即成员其实跟原对象的成员是同一块内存。而深拷贝，其实就是分配一个新的空间，然后复制原对象的内容，放到里面，改变新的对象，并不会影响原对象。像在类里面就得自己定义一个拷贝函数，然后将新对象的成员用原对象一一赋值，这样就相当于复制了一份，而不只是指向了同一块内存。
2.除此之外，还得理解下题目最后一句话的意思：
题目的意思其实就是说，不要返回形参中的结点。后面引用两个字，其实就是说我们创造一个新变量时，用已有变量去赋值，其实就是使用的这个已有变量的引用，也叫这个新变量为已有变量的引用。“赋值可以理解为引用”。下面是与函数形参相关的额外知识点：
函数形参有三种传递方式，按值传递，按指针传递，按引用传递。形参相当于局部变量，会放到栈里面，函数执行完就会被销毁。
(1)按值传递好理解，就是形参就相当于定义一个新变量，让它的值等于传入量，主要是针对基本数据类型。注意，数组不属于按值传递，数组传入会退化为指针，属于指针传递。
(2)按指针传递，其实就是将内存地址传入，可以通过指针来改变内存里的内容，进而改变变量。传入指针时，同样会copy一个新指针，执行完函数后，会被销毁，但是地址所存内容已经改变，因此可以起到改变变量的作用。这里要注意一个点，就是，形参是局部变量，但是如果说指针是形参的话，那么返回形参指针是可以的，因为销毁时只会销毁指针，而不会销毁指针指向的内存空间。而如果指针不是形参，而是在函数体内，不通过malloc/new分配，而自定义的指针，那么其会存在栈中，一旦函数体执行完，不仅会销毁指针，还会销毁指针所指的内存空间，这时再return 这个指针，也只是复制了地址，但是地址已经没有存东西了，所以return的会是不合法指针，这是不允许的。
(3)按引用传递，可以理解为直接对变量进行操作，就是用个别名而已。改变形参，就相当于改变实参。有一种特殊的引用就是const引用，目的在于，不拷贝变量，但是又不想改变变量，所以声明为const。
思路：这个题想了比较久，主要是发现拷贝的时候，总是会直接用到原链表的结点，可能是习惯了只改变指针了。random的指向，不可以用原链表的来赋值，所以需要自己连接。怎么自己连接呢？
第一步，采用的是用一个hashTable1记录原链表的结点的对应下标，这样才能在知道原结点的random指针时，找到新链表结点的random指向对应的下标。因此hashTable1就是key为结点指针，value为下标。可以理解为，对random指向的结点进行编码。
第二步，为了译码，获得新链表结点的random指向的结点，需要一个新的hashTable2来记录下标对应的新节点。因此hashTable2就是key为下标，value为对应结点指针。这样，hashTable2[
hashTable1[pHead->random]],就是新链表random指向的结点。当然，还有特殊情况，可能原链表某结点的random指向为空，那么这时，新链表对应的结点的random也应该指向为空，因此需要判断一下原链表该结点random是否指向空。
总之，就是hashTable1结点指针对应下标，hashTable2下标对应结点指针。一个编码，一个译码。
补充说明：做了leetcode上克隆图之后有了新的点。可以把编码和译码两个哈希表合为一个，直接建立旧新结点的映射。
代码如下：

    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead==nullptr)    return nullptr;
        //深拷贝
        RandomListNode*tmp=pHead;//临时链表指针
        RandomListNode* clone=new RandomListNode(-1);//头结点
        RandomListNode* tclone=clone;
        //用哈希表记录编码和译码方式
        //map<RandomListNode*,int>hashTable1;
        //map<int,RandomListNode*>hashTable2;
        //int flag=0;
        //改为用一个哈希表就行
        map<RandomListNode* ,RandomListNode* >hashTable;
        while(tmp!=nullptr){//先建立顺序链表并创建编码和译码
            tclone->next=new RandomListNode(tmp->label);
            tclone=tclone->next;
            hashTable[tmp]=tclone;
            //hashTable1[tmp]=flag;//结点指针对应下标
            //hashTable2[flag++]=tclone;//下标对应结点指针
            tmp=tmp->next;
        }
        //译码补充random
         tmp=pHead;tclone=clone->next;
        while(tclone!=nullptr){
            if(tmp->random!=nullptr)
                tclone->random=hashTable[tmp->random];
                //tclone->random=hashTable2[hashTable1[tmp->random]];
            else tclone->random=nullptr;
            tmp=tmp->next;
            tclone=tclone->next;
        }
        return clone->next;
    }

⑥JZ36 两个链表的第一个公共结点---中等

思路：
1.方法一：用哈希表记录就可以了。

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr||pHead2==nullptr)    return nullptr;//特例特判
        unordered_set<ListNode*>hashTable;ListNode* tmp=pHead1;
        while(tmp){
            hashTable.insert(tmp);
            tmp=tmp->next;
        }
        while(pHead2){
            if(hashTable.count(pHead2))    return pHead2;
            pHead2=pHead2->next;
        }
        return nullptr;
}

2.方法二：双指针的方法，通过变换指针的位置来使其相遇。有点像链表中找环那道题用的思想，都是利用的指针所走长度的和相等，从而相遇来找到重合的点。不过那道题用的快慢指针，这个题不需要。
本题的原理可以解释为，假设链表1在公共结点前一段长a，链表2在公共结点前一段长b，两链表公共长度为c，则指针走一遍链表1或链表2之后，再走另一链表，最终就会相遇。因为a+c+b=b+c+a。
图示如下：

本题在实现交换指针位置时要注意两个点：第一，要注意先判断指针能不能走，不能走了就换位置，并记录次数，能走就继续走。第二，需要格外加一个计数器，计算交换位置的次数，只能交换两次，如果两次还每遇到话，所以没有公共结点。
代码如下：

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
       if(pHead1==nullptr||pHead2==nullptr)    return nullptr;//特例特判
        ListNode* tmp1=pHead1;ListNode* tmp2=pHead2;
        int flag=0;//标记，记录交换指针次数，超过2次还没遇到证明没有公共结点
        while(tmp1!=tmp2){
            //先走再判断是否到头，然后换指针位置
            if(tmp1==nullptr){
                tmp1=pHead2;++flag;
            }
            else tmp1=tmp1->next;
            if(tmp2==nullptr){
                tmp2=pHead1;++flag;
            }
            else tmp2=tmp2->next;
            if(flag>2)   return nullptr;
        }
        return tmp1;
}

⑦JZ55 链表中环的入口结点---中等

思路图解：

代码如下：

 ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //当然可以使用哈希表记录，这里就不再写了
        //用快慢指针解决
        ListNode *fast=pHead,* slow=pHead;
        do{
            if(!fast||!fast->next)    return nullptr;
            fast=fast->next->next;
            slow=slow->next;
        }while(fast!=slow);
        fast=pHead;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }

1.注意一点，就是在第一个while处，应该xian执行内部，再判断，因为一开始的fast和slow都在起点处，判断条件肯定不通过，会跳过这步循环。所以应该先让指针动起来，离开起点，再判断。这时用do...while比较合适。
2.总结下第六第七题：似乎跟公共结点或环点有关的问题都是让两指针通过换位置，让他们走过相等的路程，从而相遇，来找到公共结点的。
A.找环时用快慢指针，快指针一次走两步，慢指针一次走一步，数学等式是(n-1)(b+c)+c=a,其中b+c是环长度，a是入环前长度。假设两指针在b处相遇，那么只要让快指针回到起点，快指针速度变为和慢指针一致，那么最后两指针就会走到环点处。因此，找环只交换快指针的位置就行。
B.而找公共结点时，是相同速度的指针，需要分别交换两个指针的位置，数学等式为a+c+b=b+c+a。
⑧JZ56 删除链表中的重复结点---较难

思路：一开始没有完全理解题意，以为是删除重复的结点，但是要保留一个，没想到题目要求的是全部删掉。所以一开始用哈希表的做法并不能实现。后来用的双指针，用probe去试探，让它遍历重复的结点并删除掉，再将其与cur拼接即可。
图解如下：

代码如下：

 ListNode* deleteDuplication(ListNode* pHead) {
        //双指针法
        //需要一个头结点
        ListNode *myhead=new ListNode(-1);
        myhead->next=pHead;
        ListNode *cur=myhead,* probe=pHead;
        while(probe){
            if(probe->next&&probe->val==probe->next->val){
                while(probe&&probe->next&&probe->val==probe->next->val){
                    ListNode *tmp=probe;
                    probe=tmp->next;
                    free(tmp);
                }
                ListNode *tmp=probe;
                probe=tmp->next;
                free(tmp);
                cur->next=probe;
            }
            else{
                probe=probe->next;
                cur=cur->next;
            }
        }
        return myhead->next;
}

试题链接：
从尾到头打印链表
链表中倒数第K个结点
反转链表
合并两个排序的链表
复杂链表的复制
两个链表的第一个公共结点
链表中环的入口结点
删除链表中重复的结点