链表经典面试题

以下的每个题都配有链接，大家可以点击进入进行练习，想了解更多知识可以关注以下个人主页

敲上瘾-CSDN博客

目录

1.反转链表

2.回文链表

3.相交链表

4.环形链表

5.合并两个有序链表

1.反转链表

        分析：首先确定函数的返回值，需要返回的是反转后的头节点，显然，返转后的头结点是原链表的尾结点，而原链表的头结点应该指向NULL。

        方法一：使用一个结构体指针数组，将每一个结点存入数组内，然后把arr[0]的下一个结点指向NULL，arr[1]的下一个结点指向arr[0]，以此类推。然后把数组最后一个元素返回。此方法空间复杂度为O(n)，时间复杂度为O(n)。

        方法二：这个题就是让我们把头结点的next指向NULL，然后把后面的每个结点的next都指向前一个结点，可以使用三个指针变量比如n1，n2，n3。n1=NULL，n2=head，n3=head->next。n2存放的是需要改变的结点，n1存放的是前一个结点(防止前结点找不到)，n3存放后一个结点(防止后结点丢失)，然后每完成一次反转，这三个指针同时往右移一位。空间复杂度为O(1)，时间复杂度为O(n)。如下图：

代码演示： 

struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL||head->next==NULL)
        return head;
    struct ListNode* n1=NULL,*n2=head,*n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}

2.回文链表

        分析：回文链表的特性是对称性，也就是它关于中间结点对称，即链表节点序列从后往前看和从前往后看是相同的，实例1从前往后看和从后往前看都是1,2,3,3,2,1。是一个回文链表。 

        方法一：使用结构体指针数组储存各节点(也可用整型数组直接储存各节点对应的值)，然后从最左边和最右边开始比较它们对应的值，然后两边同时往中间移，直到比较到最中间元素都相等为止，则为回文链表。空间复杂度为O(n)，时间复杂度为O(n)。因为该方法空间复杂度为O(n)，效率比较低，在这里就不在展示，来看方法二。

        方法二：因为回文链表具有对称性，所以把链表从中间分为两段，后半段反转后是和前半段相同的。所以现在要做的是把后半段反转，首先就需要找到中间节点，如何来找呢？，有一个巧妙的方法，就是用快慢指针，快指针每次走两步，慢指针每次走一步。这样快指针走完整个链表，慢指针刚好走完链表的一半，此时慢指针指向的位置就是链表的中间节点。然后把该节点当做头节点进行反转变成新的链表最后与前半段进行比较。空间复杂度为O(1)，时间复杂度为O(n)。

struct ListNode* Fnod(struct ListNode* head)//反转链表
{
    struct ListNode* n1=NULL,*n2=head,*n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}
bool isPalindrome(struct ListNode* head) {
    if(!head)
        return false;
    if(head->next==NULL)
        return true;
    struct ListNode* p1=head,*p2=head;
    while(p2&&p2->next)//找中间节点
    {
        p1=p1->next;
        p2=p2->next->next;
    }
    struct ListNode* fp= Fnod(p1);
    while(fp&&head)//比较
    {
        if(fp->val!=head->val)
            return false;
        fp=fp->next;
        head=head->next;
    }
    return true;
}

3.相交链表

        方法一(暴力算法)：用链表A的每一个元素与链表B比较一遍，如果出现相同的地方则链表相交，并返回该节点。空间复杂度为O(1)，时间复杂度为O(nm)。

        方法二(构造栈空间)：我们观察到的第2个特点是如果两个链表有重合节点，那么这些重合节点一定只出现在链表的尾部。如果两个单向链表有重合节点，那么从某个节点开始这两个链表的next指针都指向同一个节点。在单向链表中，每个节点只有一个 next指针，因此在第1个重合节点开始之后它们的所有节点都是重合的，不可能再出现分叉。
        由于重合节点只可能出现在链表的尾部，因此可以从两个链表的尾部开始向前比较，最后一个相同节点就是我们要找的节点。但是在单向链表中，只能从头节点开始向后遍历，直至到达尾节点。最后到达的尾节点却要最先被比较，这就是通常所说的"后进先出"。至此不难想到可以用栈来解决这个问题：分别把两个链表的节点放入两个栈，这样两个链表的尾节点就位于两个栈的栈顶。接下来比较两个栈的栈顶节点是否相同。如果相同，则把栈顶节点弹出，然后比较下一个栈顶节点，直到找到最后一个相同的节点。空间复杂度为O(n+m)，时间复杂度为O(n+m)。

        方法三(双指针)：首先遍历两个链表得到它们的长度，比如长度差为n，则比较长的链表先走n步使它们长度对齐，然后两个链表再一起走，如果有交点的话它们必然会相遇。空间复杂度为O(1)，时间复杂度为O(n+m)。

        方法四(双指针)：基于方法三还有一个更巧妙的方法，使用两个速度相同的指针p1和p2，指针p1从链表A跑完后跑链表B，指针p2从链表B跑完后跑链表A，每跑一次比较一次，因为它们路程相同，速度相同，当它们有节点的时候必然会相遇。空间复杂度为O(1)，时间复杂度为O(n+m)。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*p1=headA,*p2=headB;
    while(p1!=p2)
    {
        p1=p1!=NULL?p1->next:headB;
        p2=p2!=NULL?p2->next:headA;
    }
    return p1;
}

4.环形链表

        分析：首先我们用快慢指针来判断是否有环，快指针p2每次走两步，慢指针p1每次走一步，如果有环他们必然相遇。看似很显然，不过我们依然需要证明一下，进行深入理解(在后面图中给出证明)。

        如果没有环，即快指针会先走到NULL，直接返回NULL即可。如果有环，我们求一下环的长度，即让快指针停留在他们相遇的位置，只让慢指针走，每走一步计一次数，直到他们再次相遇，所计的数即为环的长度，记为c。

        最后再用两个指针从头开始跑，第1个指针先跑c步以后，第二个指针再开始跑，因为环的长度为c，所以第2个指针跑完一圈环后，刚好回到环的入口点与第1个指针相遇。那么这样就找到环的入口点了。

        该方法可以把它优化一下，不用计算环的长度，当快慢指针相遇时，假设慢指针走了m步，那么快指针就走了2m步。那么它们的差值(即m)就是环长度的整数倍。现在相当于慢指针p1提前走了m步，只需要再找一个慢指针p3，从头节点开始，两慢指针同时走，到它们相遇时即为环的入口点。

        当然这个题我们不能止步于此，我们试着给出以上证明，并且分析更复杂的情况(即快指针一次走3步，4步，甚至更多可不可以解决这个问题)。

慢指针一次走1步，快指针一次走3步的情况(其它情况与这个类似分析，就不在赘述)：

现在要考虑的是n为奇数c为偶数这种情况有没有可能不会同时出现？

答案是确实不会的，证明如下：

以上只是证明了用快慢指针来判断是否有环的问题。下面来证明环的入口的查找。

代码演示：

struct ListNode *detectCycle(struct ListNode *head) {
    if(!head||!head->next)
        return NULL;
    struct ListNode* s1=head,*s2=head,*k1=head;
    while(s2&&s2->next)
    {
        s1=s1->next;
        s2=s2->next->next;
        if(s1==s2)
        {
            while(k1!=s1)
            {
                k1=k1->next;
                s1=s1->next;
            }
            return k1;
        }
    }
    return NULL;
}

5.合并两个有序链表 

        方法一：使用结构体指针数组将它们有序的储存到同一个数组当中，然后在把数组的从头至尾的元素链接在一起。

         方法二：创建一个新的结构体指针变量，然后遍历两个链表，将两个链表中的节点有序的连接到新创建的节点中，构成一个新的带头链表，然后返回头结点的next。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL||list2==NULL)
        return list1==NULL?list2:list1;
    ListNode* ph=(ListNode*)malloc(sizeof(ListNode));
    ListNode* head=ph;
    while(list1&&list2)
    {
        if(list1->val<=list2->val)
        {
            ph->next=list1;
            list1=list1->next;
        }
        else
        {
            ph->next=list2;
            list2=list2->next;
        }
        ph=ph->next;
    }
    if(list1)
        ph->next=list1;
    if(list2)
        ph->next=list2;
    ph=head->next;
    free(head);
    return ph;
}

        总结以上方法我们可以发现每个链表相关的题几乎都可以构造一个结构体指针数组来解决，确实这个方法逻辑简单，更容易被我们想到，不过这种空间复杂度为O(n)的算法，不足以拿到offer。只适合像暴力算法一样把它当做为最后的选择。