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

单链表相关知识点详见数据结构——线性表的链式存储结构及函数实现C语言https://blog.csdn.net/wy_05136/article/details/159086043?spm1001.2014.3001.55011.逆置单链表1方法一借助辅助结点无限头插需要2个指针void Reverse1(Node* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.最少两个结点才需要逆置 if (Get_length(plist) 1) return; //2.申请两个指针p和qp指向第1个有效结点q指向第2个有效结点 Node* p plist-next; Node* q p-next; //因为已经保证了最少2个结点所以不会有风险 //3.将头结点的next域置为空 plist-next NULL; //4.进入while循环循环条件是p指向的结点要存在 while (p ! NULL) { //5.重新定位qq指向p结点的直接后继 q p-next; //6.将p结点头插到plist链表里面 p-next plist-next; plist-next p; //7.再让p同步到q的位置让p和q互相配合起来将后续的所有结点依次头插完毕 p q; } }2方法二不借助辅助结点需要3个指针相互配合原地进行指向方向逆置void Reverse2(Node* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.最少两个结点才需要逆置 if (Get_length(plist) 1) return; //2.申请3个指针p和q和rp指向第1个有效结点q指向第2个有效结点r指向NULL Node* p plist-next; Node* q p-next; //因为已经保证了最少2个结点所以不会有风险 Node* r NULL; //3.进入while循环之前先把第一个结点(也就是逆置之后的尾结点)的next域提前置空 p-next NULL; //4.进入while循环循环条件是q结点要存在 while (q ! NULL) { //5.通过3个指针pqr相互配合将p和q之间的箭头逆置 r q-next; q-next p; p q; q r; } //6.当while循环结束说明3个指针pqr此时已经将所有的有效结点给逆置了 // 最后只需要让头结点的next域保存此时的p的地址 plist-next p; }2.1.判断单链表是否相交突破点判断是否相交只需要看其尾结点是不是同一个结点即可。bool Intersect(Node* plist1, Node* plist2) { //0.断言:检查传入的指针是否为空 assert(plist1 ! NULL plist2 ! NULL); //1.申请两个指针分别指向两个单链表的尾结点 Node* p1 plist1; for (; p1-next ! NULL; p1 p1-next); Node* p2 plist2; for (; p2-next ! NULL; p2 p2-next); //2.判断两个单链表的尾结点是否相同若相同则是相交链表返回true不相同则返回false return p1 p2; }2.2.判断单链表是否相交如果相交返回第一个相交点如果不相交返回NULL。Node* Intersect2(Node* plist1, Node* plist2) { //0.断言:检查传入的指针是否为空 assert(plist1 ! NULL plist2 ! NULL); //1.获取两个链表的有效长度 int len1 Get_length(plist1); int len2 Get_length(plist2); //2.默认让p1指向较长的单链表的头结点让p2指向较短的单链表的头结点 Node* p1 len1 len2 ? plist1 : plist2; Node* p2 len1 len2 ? plist2 : plist1; //3.让p1先走|len1-len2|步这样p1和p2距离尾结点的长度就是一样的了 for (int i 0; i abs(len1 - len2); i) p1 p1-next; //4.让p1,p2同步向后走 // 若有相交点当p1p2时则说明两个链表相交循环结束此时p1,p2就是相交点; // 若没有相交点等p1,p2都指向末尾NULL时p1p2NULL循环结束返回NULL while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; }3.不知道头指针的情况下任意删除一个结点这个结点不能是尾结点突破点不执着于一定要释放待删除结点的内存只要我最后的链表里没有这个结点的元素即可因此我让该结点的数据域存放直接后继的元素而直接后继作为它的替死鬼。由此题目中说到这个任意删除的结点不能是尾结点因为尾结点没有直接后继它找不到替死鬼。bool Del_Node(Node* p) { //0.断言:检查传入的指针是否为空 assert(p ! NULL); //1.防止传入的指针指向的是尾结点 if (p-next NULL) return false; //2.既然p不是尾结点则找到p结点的直接后继(作为p结点的替死鬼)用指针q指向 Node* q p-next; //3.将q结点的数据域拷贝给p结点的数据域 p-data q-data; //4.跨越指针(指的是p结点把q结点跨过去)释放q结点的内存 p-next q-next; free(q); q NULL; return true; }4.判断单链表是否是回文链表bool Palindrome(Node* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.确保链表不是空链表 assert(plist-next ! NULL); //2.申请两个数组用来存放链表元素数组长度链表有效长度 int len Get_length(plist); int* arr1 (int*)malloc(len * sizeof(int)); int* arr2 (int*)malloc(len * sizeof(int)); //3.开始存放元素一个数组正着存一个数组倒着存 for (Node* p plist-next, int i 0; p ! NULL; p p-next, i) { arr1[i] p-data; arr2[len - 1 - i] p-data; } //4.从头遍历两个数组 for (int i 0; i len; i) { if (arr1[i] ! arr2[i]) return false; //若这两个数组元素不相同则说明不是回文链表 } //5.若这两个数组元素相同则说明是回文链表 return true; }5.判断单链表是否有环有环直接返回入环点没有环则返回NULLNode* Is_Circle(Node* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.最少有一个元素才可能形成环 assert(plist-next ! NULL); //2.申请两个指针快指针和慢指针让其默认都指向头结点 Node* quick plist; Node* slow plist; //3.让快慢指针各自先走一次慢指针一次走一步快指针一次走两步 slow slow-next; quick quick-next-next; //因为已经保证了最少1个结点所以不会有风险 //4.进入while循环循环条件是在快指针走到空之前看快慢指针能否再次相遇 while (quick ! NULL quick ! slow) { slow slow-next; if (quick-next NULL) return NULL; //一次走两步有风险 因为有可能第一步踏空 quick quick-next-next; } //5.while循环结束有两种情况 // 情况1 quickNULL 说明没有环 // 情况2 quick!NULL但是quickslow 说明有环 if (quick NULL) return NULL; //找入环点方法 //6.1.申请一个指针p从头结点出发 Node* p plist; //6.2.再申请一个指针q从快慢指针相遇点出发 Node* q quick; //slow也行 //6.3.让他俩同一时间保持同样的速度出发当他俩相遇时相遇的点就是入环点 while (p ! q) { p p-next; q q-next; } return p; //return q; }6.找到单链表倒数第k个结点1方法一直接推导出倒数第k个结点是正数第几个结点Node* Get_K_backwards1(Node* plist, int k) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.确保k有意义 assert(k 1 k Get_length(plist)); //2.定位结点:倒数第k个结点是正数第几个结点 int length Get_length(plist); int pos length - k 1; //3.遍历单链表获取正数第pos个结点的地址 Node* p plist; for (int i 1; i pos; i) p p-next; //4.返回地址 return p; }2方法二两个指针相互配合找到所求结点Node* Get_K_backwards2(Node* plist, int k) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.确保k有意义 assert(k 1 k Get_length(plist)); //2.申请一个指针q让q先走k步 Node* q plist; for (int i 0; i k; i) q q-next; //3.再申请一个指针p指向头结点 Node* p plist; //4.让p和q同时向后走当q走完链表后p指向的即为所求结点 while (q ! NULL) { p p-next; q q-next; } //5.返回地址 return p; }