algorithm

Algorithm(4) linked list(By input data structure)

这一块主要记录一下链表相关的一些常考题目以及解题思路。

基本知识

这一块的难点主要是考察代码的实现能力，链表相关的题目在思路上比较简单，链表上每一个元素都存储空间都是临时分配的，每一个节点在存储空间的物理位置上是不一定连续的。链表的问题，在实现的时候，最优解往往不是使用额外的数据结构，这往往需要更多的技巧（最基本的比如链表的翻转）

在分类上

  • 按照链表链接的方向，可以分为单链表以及双链表。对于单链表，每个节点只能通过其next指针指向下一个节点，双链表的每个节点，除了next指针之外，还有一个previous指针，可以指向它的前一个节点，通过当前节点，既可以找到前一个节点，也可以找到后一个节点。
  • 按照有环以及无环分类，又可以分成普通链表（无环）以及循环链表（有环），循环链表是首尾相接的链表，循环链表的最后一个元素的next指针会指向其第一个元素，循环链表的第一个元素的previous指针会指向其最后一个元素。

实现上的注意问题

  • 链表调整函数的返回值类型，根据要求，往往是节点的类型
  • 处理链表的过程中，需要采用画图的方式，来使得整个逻辑尽量清晰
  • 边界条件的处理要严格（头结点 尾节点 空节点）

链表插入和删除的注意事项

  • 特殊处理链表为空，或者链表长度为1的情况
  • 注意插入和删除的时候，要找到插入位置和删除位置的前一个节点，在头尾部进行插入和删除操作的时候需要特殊考虑
  • 双链表的时候还需要考虑previous指针的情况

单链表翻转的操作（需要同时记录 previous节点 now节点 next节点 三个位置)

  • 用临时变量记录下now节点的下一个节点的位置
  • now节点的next指针指向前一个节点 now节点变为新的head节点
  • 循环以上操作，最后返回最新的head节点

实现上的注意事项

listnode类的题目，总是做起来不爽，因为要自己定义结构体还有组链表什么的。其实还是有点不熟悉。

自己定义结构体，注意初始化的函数。

typedef struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
}ListNode;

还有就是初始化的时候 申请空间 给初始的空间赋值这些操作
ListNode *h=(ListNode*)malloc(sizeof(ListNode)); h->next=NULL;（事实上 这里的初始化赋值的操作完全可以根据链表的定义来进行，在定义的时候，就把初始化的操作写清楚了）

注意根据题目的要求，看链表在定义的时候究竟需不需要包含头结点，一般头结点就放在那里不动了，之后设置一个temp指针，来不断向后移动，用于执行具体的操作。

关于退出条件以及一些细节，在进行h->next这种操作之前，一定要判断是否h指针是否为NULL，要不然总会在莫名奇妙的地方出现问题。

一些常用的tips

  • 这块的操作确比较繁琐，在初始话的时候最好使用构造函数的形式head=new ListNode(val);以免造成忘记初始化为NULL
  • head指针太关键了，所有操作也都是从head指针开始的，不管是循环的还是非循环的，都要保存一个head指针，根据题目的实际情况判断头结点设置为空节点，还是第一个元素所在位置的节点。（比如后面的删除值为val的节点的题目）
  • 注意保存lastNode，即是当前节点的上一个节点，许多操作都是lastNode和currentNode结合起来进行的
  • 插入，删除的时候，改变指针也都是先改变后面的再改变前面的

链表遍历的注意事项

为何链表的题目容易做错，既然思路不难，关键就在规范性上，在细节上面。比如遍历链表的操作，模式很简单，但是总是忘记tail指针，直接每次去拿头节点遍历，然后发现，要保存head指针，之后又调，总之，大多数的时候都是应为细节注意不到位带来的错误，还有比如链表节点的初始化等等。在这里规范一下遍历的思路。

//给定了链表的头指针 head
//这里一定要注意 遍历的时候是用另外一个tail指针进行 头节点指针保持不变
ListNode *tail=head;
while(tail!=NULL){
	//do sth (create or some operations) for tail node 
	tail=tail->next;
}

在实际实现的时候，有好多题目会借用到两指针的相关思路

有序的环形单链表中插入新的元素

用两个index保存有当前元素和下一个元素的位置，开始的时候，一个在头结点，一个在第一个位置，之后两个指针同时向后移动，要是发现了合适的位置（insert值比前一个大 比后一个小）就插入元素。要是没有发现，就将最终的值插入到头结点和尾节点之间，此时插入的元素可能是所有元素里面最小的，也有可能是所有元素里面最大的。

如果插入元素是所有里面最小的，还是返回当前这个元素的位置，如果是所有元素里面最大的，返回原来头结点的位置。

这个题目在做的时候，总是报您的程序打印了太多的内容，暂时不知到错在哪里(估计还是哪里有死循环？？？)，以下是源码：

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class InsertValue
{
public:
    ListNode* insert(vector<int> A, vector<int> nxt, int val)
    {
        // write code here
        int i,len,num;
        len=A.size();
        int nxtIndex=0;
        int currVlue;
        ListNode *lastNode=NULL;
        ListNode *currNode=NULL;
        ListNode *head=NULL;
        if (len==0)
        {
            head=new ListNode(val);
            head->next=head;
            return head;
            
        }
        //lastNode could be the head node
        head=new ListNode(-1);
        lastNode=head;
        nxtIndex=0;
        num=0;
        while(num<len)
        {
            currVlue=A[nxtIndex];
            currNode=new ListNode(currVlue);
            lastNode->next=currNode;
            lastNode=currNode;
            num++;
            nxtIndex=nxt[nxtIndex];
        }
        //could be a circle
        if(nxtIndex==0)
        {
            currNode->next=head->next;
        }
        //debug
        ListNode *temp;
        temp=head;
        for(i=0; i<num+num; i++)
        {
            printf(" %d",temp->val);
            temp=temp->next;
        }
        putchar('\n');
        //debugok
        lastNode=head->next;
        currNode=head->next->next;
        bool ifInsert=false;
        while(true)
        {
            if (currNode->next==NULL)
            {
                break;
            }
            //problem here
            //same value but different address??
            if (currNode->next==head->next)
            {
                break;
            }
            if((lastNode->val<=val)&&(currNode->val>=val))
            {
                ListNode *insertNode=new ListNode(val);
                lastNode->next=insertNode;
                insertNode->next=currNode;
                ifInsert=true;
                break;
            }
            lastNode=lastNode->next;
            currNode=currNode->next;
        }
        if (ifInsert)
        {
            return head->next;
        }
        if(val>currNode->val)
        {
            ListNode *insertNode=new ListNode(val);
            insertNode->next=currNode->next;
            currNode->next=insertNode;
            return head->next;
        }
        else
        {
            ListNode *insertNode=new ListNode(val);
            insertNode->next=head->next;
            head->next=insertNode;
            if(currNode->next!=NULL)
            {
                currNode->next=insertNode;
            }
            return head->next;
        }
    }
};
int main()
{
    int A[10]= {1,3,4,5,7};
    int nxt[10]= {1,2,3,4,0};
    vector<int> va;
    vector<int> vnxt;
    int i;
    for(i=0; i<5; i++)
    {
        va.push_back(A[i]);
        vnxt.push_back(nxt[i]);
    }
    InsertValue iv=InsertValue();
    //debug
    ListNode *temp;
    ListNode *head;
    head=iv.insert(va,vnxt,0);
    int num=5;
    temp=head;
    for(i=0; i<num+num+num; i++)
    {
        printf(" %d",temp->val);
        temp=temp->next;
        if (temp==head){
            break;
        }
    }
    //debugok
    return 0;
}

删除链表中的节点(简单但是不容易想到 有种跳跃思维在里面)

给定一个链表中的节点node，但不给定整个链表的头结点，如何在链表中删除node?
只有一些简单的替代思路，暂时还没有更好的办法。

替代思路:
如果是双链表的情况，会比较容易处理，直接根据当前节点的preious以及next指针找到前一个元素以及后一个元素，之后把这两个元素的指针进行对应的调整，可以删除掉当前元素。

如果是单链表的情况，比如 1->2->3 这种情况，比如要删除值为2的节点，此时可以用节点3的值覆盖掉节点2之后把节点3删除，这仅仅是逻辑上的删除，不是真正意义上的删除，因为这种操作是通过值拷贝来进行的。

这种操作的问题是，无法删除最后一个节点，比如无法删除3号位置的节点。而且在实际工程中，每个节点所代表的意义并不相同，比如每个节点如果代表一个一个的服务器，这种copy可能无法把全部的依赖都copy过去，比如节点3的环境可能无法完全在节点2上重现，这个时候，把节点3删除了会带来未知问题。

代码实际上比较trick，仅仅是一种模拟的情况

class Remove {
public:
    bool removeNode(ListNode* pNode) {
        // write code here
        if(pNode->next==NULL){
            return false;
        }
        pNode->val=pNode->next->val;
        pNode->next=pNode->next->next;
        return true;
    }
};

调整链表元素的位置（partition）

给定一个链表的头结点head，再给定一个数字num，请把链表调整成节点值小于num的节点都放在链表的左边，值等于num的节点都放在链表的中间，值大于num的节点都放在链表的右边。（虽然比较简单 还是一下想不到 多少有点豁然开朗的感觉）

考察的重点代码实现不出错的能力

思路一：
使用额外的数组，将链表中的元素放到数组中。之后类似荷兰国旗问题，对数组进行一次partition，之后再还原为链表。

思路二：
思路一其实没有发挥链表的优势：拆分灵活，实质上只需要在遍历链表的时候，把原来的大链表拆分成三个小的链表就可以了，拆分之后再讲这三个小的链表串起来，灵活方便，也不容易出错。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Divide
{
public:
    int ifempty(ListNode *head)
    {
        if (head->next==NULL)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    ListNode* listDivide(ListNode* head, int val)
    {
        ListNode *heada=new ListNode(-1);
        ListNode *headc=new ListNode(-1);
        ListNode *taila=heada;
        ListNode *tailc=headc;
        ListNode *returnHead;
        ListNode *temp=head;
        if (temp->next==NULL){
            return head;
        }
        while(temp!=NULL)
        {
            ListNode *newnode=new ListNode(temp->val);
            if(temp->val<=val)
            {
                taila->next=newnode;
                taila=newnode;
            }
            else
            {
                tailc->next=newnode;
                tailc=newnode;
            }
            temp=temp->next;
        }
        if (ifempty(heada)==false)
        {
            returnHead=heada->next;
            taila->next=headc->next;
        }
        if(ifempty(heada)==true && ifempty(headc)==false)
        {
            returnHead=headc->next;
        }
        return returnHead;
    }
};
int main()
{
    int a[5]= {360,220,2};
    int val=2;
    int i;
    ListNode *head=new ListNode(360);
    ListNode *tail=head;
    ListNode *returnHead;
    for(i=1; i<3; i++)
    {
        ListNode *temp=new ListNode(a[i]);
        tail->next=temp;
        tail=temp;
    }
    tail=head;
    while(tail!=NULL)
    {
        printf(" %d",tail->val);
        tail=tail->next;
    }
    putchar('\n');
    Divide d;
    returnHead=d.listDivide(head,val);
    tail=returnHead;
    while(tail!=NULL)
    {
        printf(" %d",tail->val);
        tail=tail->next;
    }
    return 0;
}

两个链表的公共部分(这个没有要求公共部分连续 降低了一些难度)

给定两个有序链表的头结点head1以及head2，求两个有序链表的公共部分。

其实思路也很简单，就是类似于之前的两指针的思路。

是指上是两指针问题的一个链表版本的实现。

首先是前提条件判断，如果为空的时候，就直接返回空，之后index1与index2都从头开始往后遍历，如果两个元素的值相等，则打印，之后两个index全都后移，否则，值稍微小一点的那个链表的index向后移动，重复前面的逻辑。

代码实现起来倒是比较简单，注意开始时候的空值判断

class Common
{
public:
    vector<int> findCommonParts(ListNode* headA, ListNode* headB)
    {
        vector<int> common;
        if (headA->next==NULL||headB->next==NULL)
        {
            return common;
        }
        ListNode *tailA=headA;
        ListNode *tailB=headB;
        while(tailA!=NULL&&tailB!=NULL)
        {
            if(tailA->val==tailB->val){
                common.push_back(tailA->val);
                tailA=tailA->next;
                tailB=tailB->next;
                continue;
            }else if(tailA->val<tailB->val){
                tailA=tailA->next;
                continue;
            }else{
                tailB=tailB->next;
                continue;
            }
        }
        return common;
    }
};

链表局部逆序（比较灵活 综合性较强）

给定一个链表的头结点head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K格节点一组，则不调整最后的几个节点。

比如链表 1->2->3->4->5->6->7->8->null K=3 进行调整之后，就会变成3->2->1->6->5->4->7->8->null 因为最后两个元素的个数加起来没有组成3，所以最后两个节点不够一组。
说起来简单做起来难，总之有好多边界情况需要考虑，这块可能隐藏着的坑比较多。

思路一：
其实有点综合题的感觉，涉及到逆序类的题目，可以很自然的联想到逆序的操作，比如前面K个元素先入栈，之后再反向一一弹出，每次弹出的时候，需要链表的next指针进行重连，具体涉及到的细节比较多。

注意最后元素不足k个的时候，应该如何处理。
组与组之前需要经行连接，需要记下上一组中的最后一个元素。
返回调整时候链表的头结点，函数应该返回链表的头结点。

思路二：
与方法一类似，就是省去了栈的这种额外结构，依然是搜集到k个元素就进行一次k个元素之间的逆序操作。每组逆序之后的头节点和上一组已经调整好的尾节点相连。

总的来说，使用栈的话，实现上还是会简单一些，下面是相关代码，做题的时候还是要仔细一点，别把stack与vector两个结构给弄混了。。。：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class KInverse
{
public:
    ListNode* inverse(ListNode* head, int k)
    {
        ListNode *tail=head;
        ListNode *newhead=new ListNode(-1);
        ListNode *newtail=newhead;
        stack<ListNode*> help;
        while(tail!=NULL)
        {
            help.push(tail);
            tail=tail->next;
            if (help.size()==k)
            {
                //pop and link to new list
                while(help.empty()==false)
                {
                    ListNode *temp=help.top();
                    help.pop();
                    newtail->next=temp;
                    newtail=newtail->next;
                }
            }
        }
        //extra element in stack
        ListNode *lastone;
        if(help.empty()==false){
            lastone=help.top();
            help.pop();
            lastone->next=NULL;
        }
        while(help.empty()==false) {
                ListNode *temp=help.top();
                help.pop();
                temp->next=lastone;
                lastone=temp;
        }
        newtail->next=lastone;
        return newhead->next;
    }
};
int main(){
    int a[10]={1,2,3,4,5,6,7,8};
    ListNode *head=new ListNode(a[0]);
    int i;
    ListNode *tail=head;
    for (i=1;i<8;i++){
        ListNode *temp=new ListNode(a[i]);
        tail->next=temp;
        tail=tail->next;
    }
    tail=head;
    while(tail!=NULL){
        printf(" %d",tail->val);
        tail=tail->next;
    }
    putchar('\n');
    KInverse k;
    ListNode *newhead=k.inverse(head,3);
    tail=newhead;
    while(tail!=NULL){
        printf(" %d",tail->val);
        tail=tail->next;
    }
    return 0;
}

删除值为val的节点

给定一个单链表的头节点head，链表中的每个节点保存一个整数，再给定一个值val，把左右值等于val的节点全部删掉。（注意边界条件 仅有一个节点的时候怎么处理）

思路上不难，把整个过程看做是一个新链表的构造过程，还是细节，如果当前的这个节点是val，就直接抛弃，否则就接到新节点的末尾。

注意设置专用头结点的小技巧：
这个题目在给的时候，头结点的位置实际上是第一个元素，这种问题给法在实际处理的时候很不方便，应为总是要考虑第一个元素的特殊情况，后面case的处理方式无法和第一个统一起来，这个时候可以对原来的链表进行适当的“扩展”，就是扩展出一个realHead，作为真正的头结点，让realHead的next值指向第一个存储了元素的节点，即head，prev指针开始的时候就放在realHead的这个位置上，这样后面的情况处理起来就可以用一个逻辑进行了。

class ClearValue {
public:
    ListNode* clear(ListNode* head, int val) {
        // write code here
        ListNode *realHead=new ListNode(-1);
        realHead->next=head;
        ListNode *prev=realHead;
        ListNode *curr=head;
        int temp;
        while(curr!=NULL){
            temp=curr->val;
            if(temp==val){
                prev->next=curr->next;
                delete(curr);
                curr=prev->next;
            }else{
                curr=curr->next;
                prev=prev->next;
            }
            
        }
        return realHead->next;
    }
};

判断一个链表是否为回文结构（后面两种方法很有启发性）

比如：链表 1-2-3-2-1 是回文结构，返回true，链表1-2-3-1不是回文结构，返回false。

思路1

借用栈，第一次遍历，把元素压入栈中，第二次遍历，栈中元素同时也向外弹出，一次比较，如果比较到最后，所有的元素都相等，说明是回文结构。（实现上是最简单的）
代码如下，注意stack的基本操作：

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        stack<ListNode*> s;
        ListNode*tail=pHead;
        while(tail!=NULL){
            s.push(tail);
            tail=tail->next;
        }
        tail=pHead;
        ListNode*temp = NULL;
        while(tail!=NULL){
            temp=s.top();
            if (temp->val!=tail->val){
                return false;
            }
            tail=tail->next;
            s.pop();
        }
        return true;     
    }
};

思路2

思路1的升级版本，采用快指针和慢指针两个指针，慢指针一次向后移动一个元素，快指针一次向后移动两个元素，慢指针每次移动到的元素入栈。当快指针移动到末尾的时候，如果链表的个数奇数，就不入栈，如果为偶数则入栈，之后慢指针再向后移动，同时弹出栈中元素，依次比较是否相等，判断是否为回文链表。相当于是把链表左半部分折过来与链表的右半部分进行比较。

思路3

找到链表中间的位置，之后把链表右半部分逆序，之后采用两指针的思路，从链表的两端向中间的位置遍历，链表将被调整成这样的结构：1->2->3<-2<-1

random指针（较难 链表的拆分 拷贝）

一个链表结构中，每个节点不仅含有一条指向下一个节点的next指针，同时含有一条random指针，random指针可能指向链表当中的任意一个节点（可前可后），请复制这种含有random指针节点的链表。

这个题目的难点在与random指针的复制，比如新copy了一个节点，这个时候，如何让新节点的random指针指过去的元素也是新copy出来的，这是这个题目的难点所在。

思路：

  • 遍历链表，每次遍历的时候，复制一个元素在后面，比如原先的链表为1->2->3，复制操作之后变为1->1’->2->2’->3->3’，这种结构的一个特殊性，或者说是规律性就在与，新copy出来的元素的位置在原来的老元素的下一个位置（这一点是相当关键的）
  • 之后开始指针的复制，通过1’的random指针，可以找到原来1节点指向的元素位置，比如说是3，那么3的下一个位置就是3’，这个时候，就可以找到3’，将1’的random指针调整过去，依次这样进行，就可以完成所有的random指针的调整。
  • 最后一步就会把就的链表和新的链表进行拆分处理，拆成两个新的链表。
    下面是代码，不知道为内存超限了，注意一点就是第一次copy的时候，tail指针的位置要落在原来的元素上，而不是copy了之后的元素上。
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        RandomListNode* realHead=new RandomListNode(-1);
        realHead->next=pHead;
        RandomListNode* prev=realHead;
        RandomListNode* tail=pHead;
        while(tail!=NULL){
            RandomListNode* newNode=new RandomListNode(tail->label);
            newNode->next=tail->next;
            newNode->random=tail->random;
            prev->next=newNode;
            prev=tail->next;
            tail=tail->next;
        }
        
        tail=pHead;
        RandomListNode*copyNode=NULL;
        while(tail!=NULL){
            copyNode=tail->next;
            copyNode->random=copyNode->random->next;
            tail=tail->next->next;
        }
        
        prev=realHead;
        tail=pHead;
        while(tail!=NULL){
            prev->next=tail->next;
            prev=prev->next;
            tail=tail->next->next;
        }
        
        return realHead->next;
        
    }
};

判断一个单链表是否有环并找出相遇点

如何判断一个单链表中是否有环，有环的话，进入环的第一个节点，无环的话，返回空。判断单链表是否有环的操作还是挺容易的，但是找第一个节点的这个操作还是有点难，可以看之前的这个，还是死记住吧。。。关键是中间的那个方程的推导。

当然还是有简单思路的，如果没有空间复杂度的限制条件，可以采用hash表的思路进行求解，每次遍历一个元素，在hash表中将这个元素记录一下，key值可以是一个自增的index，value值可以是地址，之后如果在hash表中，发现了重复出现的元素，就说明其中有环，那么第一个重复出现的元素，也就是环开始的地方，这种方式相比于上一种，思路上是简洁明了的，实现上也是会简单许多的。

注意题目的多种解法。

稍微把之前blog中的算法做一下改动即可，前面的各种情况判断确实有点复杂，不确定重新写一次的话，还是否能够写对，前面在考虑链表长度为0和1的时候，已经考虑了许多特殊的情况。

class ChkLoop {  
public:
    int chkLoop(ListNode* head, int adjust) {
        ListNode *h1=head;
        ListNode *h2=head;
        bool cycle=false;
        int flag=0;
        if (head==NULL){
            cycle = false;
            flag=1;
        }
        if (h1!=NULL&&h1->next==h1){
            cycle =true;
            flag=1;
        }
        if (h1!=NULL&&h1->next==NULL){
            cycle = false;
            flag=1;
        }
        while(h1!=NULL&&h2!=NULL&&flag==0){
            h1=h1->next;
            if(h2->next!=NULL){
                h2=h2->next->next;
            }else{
                break;
            }
            if(h1==h2){
                cycle=true;
                break;
            }
        }
        if(cycle==false){
            return -1;
        }else{
            h1=head;
            while(h1!=h2){
                h1=h1->next;
                h2=h2->next;
            }
        }
        return h1->val;
    }
};

判断两个无环单链表是否相交

考研时候的场景真是历历在目啊。

  • 首先是遍历两个链表，得到它们的长度，m以及n，比如m>n，说明第一个链表比第二个多出m-n个节点。
  • 之后让指向第一个链表的指针向后走m-n步，这样两个链表就在同样的起点位置了。
  • 之后让指向两个链表的指针一起往后遍历，如果出现了公共的节点，说明两个链表在某个位置开始相交了。

当然还是有普通解法，就是类似上个题目一样，采用“万能的”hash表来实现，分别遍历两个链表，然后把其中的元素记录在hash表中，如果出现重复的，说明两个链表在这个位置开始相交了。如果一直没有出现重复的元素，说明两个链表不相交。

注意程序里面，最后一步的地方，先判断两个节点是否相同，然后再往下走，注意清楚逻辑顺序！

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class CheckIntersect {
int getLen(ListNode* head){
    int len=0;
    ListNode* tail=head;
    while(tail!=NULL){
        len=len+1;
        tail=tail->next;
    }
    return len;
}
public:
    bool chkIntersect(ListNode* headA, ListNode* headB) {
        // write code here
        int lena=getLen(headA);
        int lenb=getLen(headB);
        ListNode*taila=headA;
        ListNode*tailb=headB;
        int temp;
        if(lena>lenb){
            temp=lena-lenb;
            while(temp--){
                taila=taila->next;
            }
        }else{
            temp=lenb-lena;
            while(temp--){
                tailb=tailb->next;
            }
        }
        
        //move together
        while(taila!=NULL&&tailb!=NULL){
            if (taila==tailb){
                return true;
            }
            taila=taila->next;
            tailb=tailb->next;
        }
        return false;
    }
};

如何判断两个有环的单链表是否相交

如何判断两个有环的单链表是否相交，相交的话，返回第一个相交的节点，不相交的话，返回空。

当然，万能的hash表还是可以解决这个题目的。

首先要明确的一个基本概念，什么样的情况叫做链表相交，实际上更准确的表述是说，两个链表，从某个节点开始之后，剩下的部分都开始重合了，不存才那种”X”形式的相交，因为根据链表的结构，不会有两个next指针，只能是类似”Y”形的这种情况。或者是Y形后面接一个环的形状，再或者是一个环，然后分出两个小枝，两个链表在环的不同节点位置入环。

更高效的思路，首先是判断两个链表的环的起始的节点，具体方法可以根据上面的题目中的思路，比如两个如环节点分别是head1与head2

  • 如果head1=head2，两个链表可能在入环之前就出现相交，这个时候按照上上题的方式，只不过遍历的终止节点为head1=head2
  • 如果head1！=head2 可能是两个有换的链表根本不相交，或者如环节点是大环上的两个节点，这个时候从head1开始遍历，如果在遍历过程中找到了head2，说明是第二种情况，返回head1或者是head2都是可以的，如果在遍历的过程中，没有找到head2，又回到了head1节点，说明两个环形链表是不相交的。
    没有在规定时间运行完？？(需要把上一个题目的程序修改下，结束标志由NULL变为公共元素)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
*/
class ChkIntersection {
    
    int getLen(ListNode* head,ListNode*common){
    int len=0;
    ListNode* tail=head;
    while(tail!=common){
        len=len+1;
        tail=tail->next;
    }
    return len;
}
    bool chkIntersect(ListNode* headA, ListNode* headB,ListNode*common) {
        // write code here
        int lena=getLen(headA,common);
        int lenb=getLen(headB,common);
        ListNode*taila=headA;
        ListNode*tailb=headB;
        int temp;
        if(lena>lenb){
            temp=lena-lenb;
            while(temp--){
                taila=taila->next;
            }
        }else{
            temp=lenb-lena;
            while(temp--){
                tailb=tailb->next;
            }
        }
        
        //move together
        while(taila!=common&&tailb!=common){
            if (taila==tailb){
                return true;
            }
            taila=taila->next;
            tailb=tailb->next;
        }
        return false;
    }  
    
    
    ListNode* detectCycle(ListNode* head) {
        ListNode *h1=head;
        ListNode *h2=head;
        bool cycle=false;
        int flag=0;
        if (head==NULL){
            cycle = false;
            flag=1;
        }
        if (h1!=NULL&&h1->next==h1){
            cycle =true;
            flag=1;
        }
        if (h1!=NULL&&h1->next==NULL){
            cycle = false;
            flag=1;
        }
        while(h1!=NULL&&h2!=NULL&&flag==0){
            h1=h1->next;
            if(h2->next!=NULL){
                h2=h2->next->next;
            }else{
                break;
            }
            if(h1==h2){
                cycle=true;
                break;
            }
        }
        if(cycle==false){
            return NULL;
        }else{
            h1=head;
            while(h1!=h2){
                h1=h1->next;
                h2=h2->next;
            }
        }
        return h1;
    }
public:
    bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
        // write code here
        ListNode * pointA=detectCycle(head1);
        ListNode * pointB=detectCycle(head2);
        if (pointA==NULL||pointB==NULL){
            return false;
        }
        
        if(pointA==pointB){
            return chkIntersect(head1,head2,pointA);
        }else{
             ListNode*curr=pointA->next;
             while(curr!=pointA){
               if (curr==pointB){
                return true;
            }
        }
        return false;
        }
       
    }
    
};

判断两个单链表是否相交（综合题目）

给定两个单链表的头结点head1以及head2，如何判断两个链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。

这个题目的关键之处，是不确定两个链表是否为有环链表，还是无环链表。所以只要分类讨论即可，实际上是链表相交类题目的一个综合。

推荐文章