链表面试题集合 淡淡的烟草味﹌ 2022-05-09 00:18 147阅读 0赞 链表面试题: 1. 比较顺序表和链表的优缺点,说说它们分别在什么场景下使用? * 顺序表一般用于查找,可随机访问; * 链表一般用于增删改,不可随机访问; * 如果数据元素不多,两种方式没有太大的差别 * 如果数据元素不定,建议使用链表 * 顺序表的CPU高速缓存效率高,而单链表CPU高速缓存效率低。 链表的基本操作如下: #include "List.h" void InitLinkList(pList* pplist) { (*pplist) = NULL; } pNode BuyNode(DataType d) { pNode newNode = (pNode)malloc(sizeof(Node)); if (newNode == NULL) { perror("malldc error"); exit(EXIT_FAILURE); } newNode->data = d; newNode->next = NULL; return newNode; } void DestroyLinkList(pList* pplist) { assert(pplist); pNode cur = NULL; cur = *pplist; while (cur) { pNode del = cur; cur = cur->next; free(del); del = NULL; } *pplist = NULL; } void PushBack(pList* pplist, DataType d) { assert(pplist); pNode newNode = BuyNode(d); if ((*pplist) == NULL) { *pplist = newNode; } else { pNode cur = NULL; cur = *pplist; while (cur->next) { cur = cur->next; } cur->next = newNode; } } void PopBack(pList* pplist) { assert(pplist); if ((*pplist) == NULL) { printf("链表为空!\n"); return; } else { pNode cur = NULL; pNode del = NULL; cur = *pplist; del = cur->next; while (cur->next->next) { cur = cur->next; del = cur->next; } cur->next = del->next; free(del); del = NULL; } } void PushFront(pList* pplist, DataType d) { pNode newNode = BuyNode(d); assert(pplist); if ((*pplist) == NULL) *pplist = newNode; else { pNode cur = *pplist; newNode->next = cur; *pplist = newNode; } } void PopFront(pList* pplist) { assert(pplist); if ((*pplist) == NULL) { printf("链表为空!\n"); return; } else { pNode del = NULL; del = *pplist; *pplist = (*pplist)->next; free(del); del = NULL; } } pNode Find(pList plist, DataType d) { if (plist == NULL) { printf("链表为空!\n"); return NULL; } else { pNode cur = plist; while (cur) { if (cur->data == d) { return cur; } cur = cur->next; } return NULL; } } void Insert(pList* pplist, pNode pos, DataType d)//在指定位置之前插入一个值 { assert(pplist); assert(pos); assert(*pplist); pNode newNode = BuyNode(d); if (pos == (*pplist)) { newNode->next = *pplist; *pplist = newNode; } else { pNode cur = *pplist; while (cur&&cur->next != pos) { cur = cur->next; } if (cur) { newNode->next = pos; cur->next = newNode; } } } void Erase(pList* pplist, pNode pos)//指定位置删除 { assert(pplist); assert(pos); if ((*pplist) == NULL) { return; } if ((*pplist) == pos) { *pplist = pos->next; free(pos); pos = NULL; } else { pNode cur = *pplist; while (cur&&cur->next != pos) { cur = cur->next; } if (cur) { cur->next = pos->next; free(pos); pos = NULL; } } } void Remove(pList* pplist, DataType d) { assert(pplist); pNode cur = *pplist; if ((*pplist) == NULL) { return; } if ((*pplist)->data == d) { *pplist = cur->next; free(cur); cur = NULL; } else { pNode del = cur; while (cur&&del->data != d) { cur = cur->next; del = cur->next; } if (cur) { cur->next = del->next; free(del); del = NULL; } } } //void ReMoveP(pList* pplist, DataType d) //{ // pNode pCur = NULL; // pNode pre = NULL; // assert(pplist); // if (NULL == (*pplist)) // { // return; // } // pCur = (*pplist); // // while (pCur) // { // pNode pDel = NULL; // if (pCur->data == d) // { // if ((*pplist)->data == d) // { // pCur = *pplist; // *pplist = (pCur)->next; // free(pCur); // pCur = *pplist; // } // else // { // pre->next = pCur->next; // free(pCur); // pCur=pre; // // } // } // else // { // pre = pCur; // pCur = pCur->next; // } // } //} void RemoveAll(pList* pplist, DataType d) { assert(pplist); pNode cur = *pplist; if ((*pplist) == NULL) { return; } pNode pre = *pplist; while (cur) { if ((*pplist)->data == d) { cur = *pplist; *pplist = (cur)->next; free(cur); cur = *pplist; } else if (cur->data == d) { pre->next = cur->next; free(cur); cur = pre->next; } pre = cur; cur = cur->next; } } void PrintLinkList(pList plist) { pNode cur = plist; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } int GetListLength(pList plist) { int count = 0; pNode cur = plist; while (cur) { count++; cur = cur->next; } return count; } 2. 从尾到头打印单链表 * 递归调用 void PrintTailToHead1(pList plist)//递归逆序打印单项链表 { if (plist == NULL) return; PrintTailToHead1(plist->next); printf("%d ", plist->data); } * 非递归,时间复杂度O(n^2)。 void PrintTailToHead2(pList plist)//非递归逆序打印单项链表 { pNode tail = NULL; pNode cur = plist; if (plist == NULL) return; while (plist != tail) { while (cur->next != tail) { cur = cur->next; } printf("%d ", cur->data); tail = cur; cur = plist; } } 3. 删除一个无头单链表的非尾节点 ![70][] void EraseNotTailNode(pNode pos) { assert(pos); assert(pos->next); pNode del = NULL; del = pos->next; pos->data = pos->next->data; pos->next = del->next; free(del); del = NULL; } 4. 在无头单链表的一个节点前插入一个节点 ![70 1][] void InsertNode(pList* pplist, pNode pos, DataType d)//在无头单链表的一个节点之前插入一个节点 { assert(pplist); assert(pos); assert(*pplist); pNode newNode = BuyNode(pos->data); newNode->next = pos->next; pos->next = newNode; pos->data = d; } 5. 单链表实现约瑟夫环 方法一: ![70 2][] int pLinkNodeJosephCycle(pList * pplist, int num) { pList tmp = NULL; pList p = NULL; p = (*pplist); tmp = (*pplist); while (tmp->next) { tmp = tmp->next; } tmp->next = (*pplist); while ((*pplist) != (*pplist)->next) { for (int i = 1; i < num - 1; i++) { (*pplist) = (*pplist)->next; } p = (*pplist)->next; (*pplist)->next = p->next; free(p); p = NULL; (*pplist) = (*pplist)->next; } return (*pplist)->data; } 方法二: ![70 3][] void JosephCycle(pList * pplist, int num) { pList p = NULL; p = (*pplist); while (p!=p->next) { pNode del = NULL; int count = num; while(--count) { p=p->next; } printf("删除:%d\n",p->data); del=p->next; p->data = del->data; p->next = del->next; free(del); del = NULL; } } 6. 逆置/反转单链表 ![70 4][] void ReverseList(pList* pplist) { pList q = (*pplist); pList p = q->next; while (p) //当p指向NULL时,表明倒置完成,退出循环 { q->next = p->next; p->next = (*pplist); (*pplist) = p; p = q->next; } } 7. 单链表排序(冒泡排序) void BubbleSort(pList * pplist) { assert(pplist); assert(*pplist); pList q = NULL; pList p = NULL; for (int i = 0; i < GetListLength(*pplist); i++) { pList q = (*pplist); pList p = q->next; for (int j = 0; j < GetListLength(*pplist) - i - 1; j++) { while (p) { if (q->data < p->data) { DataType tmp = q->data; q->data = p->data; p->data = tmp; } p = p->next; q = q->next; } } } } 8. 合并两个有序链表,合并后依然有序 //递归 pNode Merge_R(pList plist1, pList plist2)//递归合并两个有序链表 { pNode cur1 = plist1; pNode cur2 = plist2; pNode newlist = NULL; if (cur1 == cur2) return NULL; if (cur1 == NULL) return cur2; if (cur2 == NULL) return cur1; if (cur1->data < cur2->data) { newlist = cur1; newlist->next = Merge_R(cur1->next,cur2); } else { newlist = cur2; newlist->next = Merge_R(cur1,cur2->next); } return newlist; } pNode Merge(pList plist1, pList plist2)//非递归合并两个有序链表 { pNode cur1 = plist1; pNode cur2 = plist2; pNode head = NULL; pNode tail = NULL; if (cur1 == NULL&&cur2 == NULL)//两条都为空不合并 return NULL; if (cur1 == cur2) return cur1; if (cur1 == NULL) return cur2; if (cur2 == NULL) return cur1; if (cur1->data > cur2->data) { head = cur1; cur1 = cur1->next; } else { head = cur2; cur2 = cur2->next; } head->next = NULL; tail = head; while (cur1 != NULL&&cur2 != NULL) { if (cur1->data > cur2->data) { tail->next = cur1; cur1 = cur1->next; } else { tail->next = cur2; cur2 = cur2->next; } tail->next->next = NULL; tail = tail->next; } if (cur1 == NULL) { tail->next = cur2; } else tail->next = cur1; return head; } 9. 查找单链表的中间节点,要求只能遍历一次链表 ![70 5][] pNode FindMidNode(pList plist)//找中间节点 { pList fast = NULL; pList slow = NULL; if (NULL == plist) { return NULL; } else { //快慢指针 slow = plist; fast = plist; while ((NULL != fast) && (NULL != fast->next)) { slow = slow->next; fast = fast->next->next; } return slow; } } 10. 查找单链表的倒数第k个节点,要求只能遍历一次链表 pNode FindLastKNode(pList plist, int k) { if ((NULL == plist) || (k <= 0)) { return NULL; } else { pNode fast = plist; pNode slow = plist; //利用快慢指针,让快指针先走K-1步,然后两指针同时走,直到快指针指向的下一个结点为空为止 while (--k) { fast = fast->next; if (NULL == fast) { return NULL; } } while (NULL != fast->next) { fast = fast->next; slow = slow->next; } return slow; } } 11. 判断单链表是否带环?若带环,求环的长度?求环的入口点?并计算每个算法的时间复杂度&空间复杂度。 pNode CheckCycle(pList pList) { if ((NULL == pList) || (NULL == pList->next)) { return NULL; } else { pNode pFast = pList->next->next; pNode pSlow = pList->next; while (pFast != pSlow) { if (NULL == pFast) { return NULL; } else { pFast = pFast->next; pSlow = pSlow->next; if (NULL == pFast) { return NULL; } else { pFast = pFast->next; } } } return pFast; } } int GetCircleLength(pNode meet) { if (NULL == meet) { return 0; } else { int count = 1; pNode pnode = meet; while (meet != pnode->next) { pnode = pnode->next; count++; } return count; } } pNode GetCycleEntryNode(pList plist, pNode meetNode) { pNode pnode = plist; if ((NULL == plist) || (NULL == meetNode)) { return NULL; } while (pnode != meetNode) { pnode = pnode->next; meetNode = meetNode->next; } return pnode; } 12. 判断两个链表是否相交,若相交,求交点。(假设链表不带环) int CheckCross(pList p1, pList p2) { if((p1==NULL)||(p2==NULL)) return 0; pNode end1=p1; pNode end2=p2; while(end1->next!=NULL) end1=end1->next; while(end2->next!=NULL) end2=end2->next; if(end1==end2) return 1; else return 0; } 13. 判断两个链表是否相交,若相交,求交点。(假设链表可能带环)【升级版】 ![70 6][] [70]: /images/20220509/5ee6046018f54292bbb3ab746267273c.png [70 1]: /images/20220509/9f63eea3804e4694b0915e7e2bc100d7.png [70 2]: /images/20220509/9fbe585638504aeeb19bbc9769a9eb07.png [70 3]: /images/20220509/afced93be7aa401ebdaecc7e3ffb0870.png [70 4]: /images/20220509/d0207b5e61a243b1a423a05ab92d998f.png [70 5]: /images/20220509/18be86e65f684cb9a8417975977ac1f2.png [70 6]: /images/20220509/eba547868a494d0dad91bf13a95ead5c.png
还没有评论,来说两句吧...