[数据结构与算法]链表面试题

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    //迭代法列表反转
    ListNode* reverse(ListNode* node)
    {
        ListNode *prev=NULL;
        ListNode *nxt;
        while(node!=NULL)
        {
            nxt=node->next;
            node->next=prev;
            prev=node;
            node=nxt;
        }
        return prev;//注意这里返回的是prev，而while里面是node
    }
    bool isPail(ListNode* head) {
        if(head==NULL) return -1;
        if(head->next==NULL) return true;
        //有两个节点
        if(head->next->next==NULL) return head->val==head->next->val?true:false;
        //三个节点 
        ListNode *fast,*slow;//快慢指针：奇数返回中点，偶数返回上中点（少于三个节点的时候都返回的是head节点）
        slow=head;
        fast=head->next;
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *pH=head;
        ListNode *pT=reverse(slow->next);//pT是反转以后的节点
        ListNode *pT2=pT;
        slow->next=NULL;//中节点末尾接一个NULL，构造成新的链表
        bool res=true;
        while(pH!=NULL&&pT!=NULL)
        {
            if(pH->val!=pT->val)
            {
                res=false;
                break;
            }
            pH=pH->next;
            pT=pT->next;
            
        }
        
        reverse(pT2);
        
        return res;
    }
};

复制特殊链表

一种特殊的单链表节点类描述如下

class Node {

int value;

Node next;

Node rand; （多了一条指针）

Node(int val) { value = val; }

}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。

给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

【要求】

时间复杂度O(N)，额外空间复杂度O(1)

利用哈希表把原来的结构全部存起来。

【算法】复制含有随机指针节点的链表 - 云+社区 - 腾讯云 (tencent.com)

进阶解法

思路

1、拷贝节点，例如对于 1->2->3->4 我们插入每个节点的后面插入其copy节点，使之为 1->1'->2->2'->3->3'->4->4' 2、那么我们通过找到源节点，即可找到其copy节点的位置（源节点.next），相当于哈希表的作用 3、最后根据原链表的rand关系，链接copy节点的rand指针 4、最后将链表拆分为原链表和copy链表

先复制节点，达到哈希表的作用，然后利用原链表的rand、next关系进行重新连接，最后一个一个拆分，因为一个隔一个是自己复制的

注意：一定要把rand复制完再进行分裂，不然后面的元素要连在前面的节点上，会找不到的

链表找环?

?基础解法：hash set，先查询每个节点，节点不在set里就加入；第一个查询到已经存在在set里的节点就是第一个入环节点；

快慢指针：使初始的slow、fast指针不在同一位置，有环的链表，slow、fast会相遇（所以一开始的slow、fast不要指在同一位置），然后让fast指针回到远点，slow和fast同时一步一步前进，再次相遇的节点就是入环节点。

单链表只有一个next方向，意味着入环节点只有一个，不会进了再出各种复杂的结构

链表相交

节点相交，相交的节点与节点的值无关，只与节点的内存大小有关。

基础解法：哈希表：把一个链表全放入hash set，然后遍历另一个链表看是否在set中存在，有的话就是第一个相交节点

进阶解法：分别遍历链表，找到链表的长度，末尾节点，

链接：https://www.nowcoder.com/questionTerminal/db55f7f21127403cb268ffad9d23af37
来源：牛客网

大体流程分两部分：
第一部分——判断单个链表是否有环
使用两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步；
若快指针最后变为空，则单链表为无环单链表，返回空指针；
若快慢指针在某一时刻指向同一节点，即二者完全一样，则为有环单链表，
此时让快指针重新指向链表头结点，然后快慢指针均一次走一步，
当快慢指针再次相同时，则此节点即为链表入环节点，将其返回。
第二部分——判断链表是否相交
情况一：两链表中一个为有环链表，一个为无环链表，则此时两链表一定不相交，返回空即可；
情况二：两个链表都是无环链表，此时有两种情况，1）两个无环链表相交；2）两个无环链表不相交；
首先遍历两链表，分别得到两个链表的长度，如果两个末尾节点内存地址不同，不可能相交；
取两个长度的差值，然后让长链表先遍历差值长度，此时长链表剩余部分与短链表长度相同，
然后两条链表同时遍历，直到遇到相同节点为止，若相同节点为空，则两链表不相交，返回空，
否则两链表相交，返回相交节点即可；
情况三：两个链表都是有环链表，此时有三种情况，1）两个有环链表不相交；2）两个有环链表相交，且交点在环外；3）两个有环链表相交，且交点在环内。
首先获得两个链表的入环节点，若入环节点相同，则可转变为情况二，此时将入环节点作为链表的终止节点即可；若两个入环节点不同，以一个入环节点开始遍历，若遍历一遍过程中都没有遇见另一个入环节点，则两链表不相交，返回空，若遇到另一入环节点，则说明两链表相交，此时返回任意一个入环节点即可。

代码可参考：?

数据结构与算法 -- 返回两个链表的相交的第一个节点_牛客博客 (nowcoder.net)??

我的leetcode提交?

找单链表的入环节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //找到链表第一入环节点，无环返回NULL
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return NULL;

        //fast的节点初始值要在slow节点的初始值
        ListNode *slow=head->next;
        ListNode *fast=head->next->next;
        while(fast!=NULL&&fast->next!=NULL&&slow!=fast)
//因为有环，不会走到空，不用判断.!!!因为要写slow和fast相等的判断条件，所以初始值要让fast比slow快一
        {
            //也可以把fast、fast->next的判空放到这里，如果为空直接返回NULL但其实都是一样的，重复的代码少了些
            slow=slow->next;
            fast=fast->next->next;
        }
        if(fast==NULL||fast->next==NULL) return NULL;//无环
       //有环
        fast=head;
        while(fast!=slow)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

?

?找两个无环链表的公共部分

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL) return NULL;
         //遍历两个链表，得到长短链表
        int n=0;
        ListNode *pHA=headA;
        ListNode *pHB=headB;
        while(pHA!=NULL)//如果是有环链表，这里的NULL就应该改成第一个入环节点
        {
            n++;
            pHA=pHA->next;
        }
          while(pHB!=NULL)
        {
            n--;
            pHB=pHB->next;
        }

        pHA=n>0?headA:headB;//pHA指向长链表
        pHB=pHA==headA?headB:headA;
        n=abs(n);
        while(n!=0)
        {
            pHA=pHA->next;//长链表遍历差值长度
            n--;
        }
        while(pHA!=NULL&&pHA!=pHB)
        {
            pHA=pHA->next;
            pHB=pHB->next;
        }
        if(pHA==NULL) return NULL;
         return pHA;
            
        
    }
};

删除链表中的某一个节点

给出了给定的节点，那么把下一个节点的值赋值到给定节点，然后直接让给定节点的next赋值成下下个节点；//借尸还魂

但是本身这个节点没有被删除，且无法删除最后一个节点。

要删除某一个节点，一定要给出头结点。