数据结构——单链表常见面试习题

单链表相关知识详见：

https://blog.csdn.net/2401_89246663/article/details/159115809?spm=1001.2014.3001.5502

以下单链表习题中会调用到单链表的函数

//获取有效长度
int Get_Length(Node* plist) {
	assert(plist != NULL);
	Node* p = plist;
	int length = -1;
	while (plist->next != NULL)length++;
	return length;
}

1.单链表的逆置：

  方法1：借助辅助节点无限头插（需要两个指针)

    思路：

      （1）先将辅助节点与第一个有效节点的连接断开也就是将辅助节点的next域置为空

      （2）在申请两个指针p和q，让p初始化指向第一个有效节点，让q初始化指向第二个有效节点

           （注意：在单链表中至少含有两个有效节点才能进行逆置，所以在代码之前要进行合理判断）

      （3）让p指向的节点与其后继断开，也就是将p的next域置为空 

      （4）此时将p指向的这个节点与辅助节点相结合，此时在新的逆置的链表中只有辅助节点和一个有效节点，所以此时只需要将辅助节点的next域改为此时p指向节点的地址。

       （5）此时让p指向的节点变为p指向节点的后继，此时也就是q指向的节点，在让q指向q的后继（此时p和q实现了同步向后）

       （6）让p此时指向的节点与其后继断开，也就是将p的next域置为空

       （7）让p这个节点与辅助节点以及此时已经在逆置的链表中的第一个有效节点结合，让p的next域变为此时辅助节点的next域也就完成了与新后继的连接，再让辅助节点的next域置为此时q的地址

       （8）循环5~7步骤直到p走到最后一个节点，也就是p不为空的时候

图文表达：

代码体现：

void Reverse1(Node* plist)
{
    //0.最少两个节点才逆置
    if (Get_Length(plist) < 2)
    {
        return;
    }
    //1.申请两个指针p和q，p初始化指向第一个有效节点,
    // q初始化指向第二个有效节点(因为已经保证了最少两个节点)
    Node* p = plist->next;
    Node* q = p->next;
    //2.将辅助节点(头结点)的next置为NULL
    plist->next = NULL;
    //3.进入while循环，循环条件是p指向的节点得存在
    while (p != NULL)
    {
        q = p->next;
        //4.将p指向节点头插到plist链表里面
        p->next = plist->next;
        plist->next = p;
        //5.再让p同步到q的位置，让p和q互相配合起来，将后续的所有节点依次头插完毕
        p = q;
    }
}

 方法2：不借助辅助节点 需要三个指针 p q r

思路：

（1）申请三个指针p q r，让p指向第一个有效节点.让q指向第二个有效节点，让r指向第3个可能存在的节点（因为至少含有两个有效节点才能逆置）

（2）让p的next域置为空，让q的next域置为p的地址

（3）让p此时指向q指向的节点，让q指向r指向的节点，r指向它的后继

（4）让q的next域置为p的地址

（5）重复3·4操作直到p指向节点为空

图文表示：

代码表示：

void Reverse2(Node* plist)
{
    //0.最少两个节点才逆置
    if (Get_Length(plist) < 2)
    {
        return;
    }
    //1.申请3个指针p和q和r，p初始化指向第一个有效节点,
    // q初始化指向第二个有效节点(因为已经保证了最少两个节点)
    // r初始化指向NULL
    Node* p = plist->next;
    Node* q = p->next;
    Node* r = NULL;
    //1.5 进入while循环之前，先把第一个节点(也就是逆置之后的尾结点)的next提前置为NULL
    p->next = NULL;
    //2.进入while循环，循环条件是q指向的节点得存在
    while (q != NULL)
    {
        //3.通过三个指针pqr的互相配合，将p和q之间的箭头逆置
        r = q->next;
        q->next = p;//原地逆置
        p = q;
        q = r;
    }
  //4.当while循环结束，说明3个指针pqr此时已经将所有的有效节点给逆置了，
  // 最后只需要让辅助节点坐享其成，也就是最后只需要让辅助节点的next保存此时p的地址
  plist->next = p;

2.找到链表倒数第k个节点

思路：

（1）申请两个指针p q，同时初始化为辅助节点的地址

（2）p不动，让q向后走k步，

（3）p和q同时向后走，直到q指向节点为空，此时p指向的节点就是我们要找的节点

图文表示：

代码表示：

Node* Get_K_backwards(Node* plist, int k)
{
    //assert
    assert(k >= 1 && k <= Get_Length(plist));
    Node* p = plist;
    Node* q = plist;
    for (int i = 0; i < k; i++)
        q = q->next;
    while (q != NULL)
    {
        p = p->next;
        q = q->next;
    }
    return p;
}

3.判断两个单链表是否存在交点：

思路：申请两个指针p q,分别从这两个单链表的辅助节点出发直到p q都走到了尾节点判断p q指向的尾结点的地址是否相同，如果相同则两个单链表相交如果不相同则不相交。

代码表示：

bool Intersect(Node* plist1, Node* plist2) {
	//只需要看其尾结点是不是同一个节点
	Node* p1 = plist1;
	Node* p2 = plist2;
	for (;p1->next != NULL;p1 = p1->next);
	for (;p2->next != NULL;p2 = p2->next);
	return p1 == p2;}

4.如果两个单链表相交返回第一个相交点，如果不相交则返回NULL：

思路：

（1）获取两个链表的长度

（2）申请两个指针p1 p2，如果两个链表一样长就让p1 p2随便随意分别指向这来两个单链表的辅助节点地址，如果不一样长让p1指向较长的链表的辅助节点，则p2就指向较短的那个

（3）得到两个链表的长度差

（4）让p1向后走长度差步

（5）如果p1 p2的地址不相等，两个指针就同时向后走

代码

表示：

Node* Intersect2(Node* plist1, Node* plist2)
{
    int len1 = Get_Length(plist1);
    int len2 = Get_Length(plist2);
    //默认让P1指向较长的单链表开始位置 
    Node* p1 = len1 > len2 ? plist1 : plist2;
    Node* p2 = len1 > len2 ? plist2 : plist1;
    //代码指向到这里，此时p1一定默认指向了较长的那个单链表的开始位置
    //                此时p2一定默认指向了较短的那个单链表的开始位置
    for (int i = 0; i < abs(len1 - len2); i++)
        p1 = p1->next;
    //代码指向到这里,p1和p2距离尾结点的长度是一样的
    while (1)
    { 
        if(p1!=p2){
        p1 = p1->next;
        p2 = p2->next;}
    }
else return p1;}
  return NULL;
}

5删除节点：

思路：

（1）申请一个指针q让q指向待删除节点的后继

（2）让q的数据域中的值覆盖到待删除节点的数据域

（3）将待删除节点的next域置为q的next域

（4）再将q释放掉

（注：因为在打印过程中，我们只在乎数据的呈现，不关心所存的地址，所以可以将数据域进行覆盖，转换删除节点的固有思维）

代码表示：

bool Del_Node(Node* p)
{
    //1.防止其是尾结点
    if (p->next == NULL)
        return false;
    //2.既然不是尾结点，则找到该节点的下一个节点(替死鬼)用指针q指向
    Node* q = p->next;
    //3.将下家的数据域拷贝给我当前节点的数据域
    p->data = q->data;
    //4.跨越指向+释放
    p->next = q->next;
    free(q);
    q = NULL;
    return true;
}

6.判断是不是回文链表

思路：

（1）获取链表长度len

（2）定义两个数组，此时数组只能用malloc来申请内存，因为数组中的[]只能是常量，len为一个变量。

（3）定义一个指针p初始化为第一个有效节点

（4）依次向后遍历，直到p指向的节点为空，在遍历过程中将数据域中的值，让第一个数组从前向后依次放入，让第二个数组从后向前依次放入

（5）从前向后依次判断数组元素是否有不相同，如果不同返回false,如果相同返回true

7代码表示：

bool Palindrome(Node* plist)
{
    int len = Get_Length(plist);
    int* arr1 = (int*)malloc(len * sizeof(int));
    int* arr2 = (int*)malloc(len * sizeof(int));
    Node* p = plist->next;
    int i = 0;
    while (p != NULL)
    {
        arr1[i] = p->data;
        arr2[len - 1 - i] = p->data;
        p = p->next;
        i++;
    }
    for (int i = 0; i < len; i++)
    {
        if (arr1[i] != arr2[i])
        {
            return false;
        }
    }
    return true;
}

7.判断链表是否有环，如果有环，则返回入环点，如果没有返回NULL;

思路：

（1）申请两个快慢指针 让其都从辅助节点出发

（2）慢指针一次走一步，快指针一次走两步

（3）在快指针走到空地址之前，快慢指针能否相遇

（4）当快指针与慢指针再次相遇时说明此时快指针以及比慢指针多走了一个环了

如果有环就要找入环点，找到入环点的数学推理如下

Node* Is_Circle(Node* plist)
{
    //0.安全判断
    assert(plist != NULL);
    assert(plist->next != NULL);//最少有一个元素，才可能形成环
    //1.申请两个指针，快指针和慢指针，让其默认都指向辅助节点(头结点)
    Node* quick = plist;
    Node* slow = plist;
    //2.让快慢指针各自先动一次(慢指针一次动一步，快指针一次动两步)
    slow = slow->next;
    quick = quick->next->next;
    //3.进入while循环，循环条件是，在快指针遇到NULL之前，看快慢指针是否能再次相遇
    while (quick != NULL && quick != slow)
    {
        slow = slow->next;
        //quick = quick->next->next;//一次走两步 有风险 因为有可能第一步踏空‘
        quick = quick->next;
        if (quick != NULL)
            quick = quick->next;
    }
    //4.上面while循环结束，有两种情况：情况1：qucik==NULL 说明没有环
    //                                 情况2：qucik!=NULL但是quick==slow 说明有环
    if (quick == NULL)
        return NULL;
    //代码执行到这一行，说明一定有环
    //找入环点方法：
    //1.申请一个指针p从头结点出发
    Node* p = plist;
    //2.再申请一个指针q从快慢指针相遇点出发
    Node* q = quick;//slow也行
    //3.让他俩同一时间保持同样的速度出发，当他俩相遇时，相遇的点就是入环点
    while (p != q)
    {
        p = p->next;
        q = q->next;
    }
    return p;//return q;
}