常见链表面试题

头文件以及定义的节点都在上一篇的单链表功能实现里面有写

逆序打印单链表

递归方式简洁明了

void linklist_reverseprintf(linklist *head) { if(head == NULL) { return;//空链表 } linklist_reverseprint(head->next); printf("[%c|%p]\n",head->data,head); }

不允许遍历链表，在pos之前插入

void swap(linktype *a,linktype *b) { linktype t = *a; *a = *b; *b = t; } void linklist_insertbefore(linklist **head,linklist *pos,linktype value) { if(head == NULL) { return;//非法输入 } if(*head == NULL) { return;//空 } if(*head->next == NULL) { linklist_pushhead(head,value); //如果只有一个元素就调用头插函数 } else { linklist *newnode=creat(value); newnode->next=pos->next; pos->next=newnode; swap(&pos->data,&newnode->data); } }

单链表的逆置

void linklist_nizhi(linklist **head) { if(head == NULL) { return; } if(*head == NULL) { return;//空链表 } if(*head->next == NULL) { return *head; } else { linklist *cur = *head; while(cur->next != NULL) { linktype value = cur->next->data; linklist_pop1(head,cur->next); linklist_pushfront(*head,value) } return *head; } }

单链表的冒泡排序

void linklist_bubble(linklist **head) { if(head == NULL) { return;//非法输入 } if(*head == NULL) { return;//空 } else { linklist *cur = *head; linklist *tail = NULL; linklist *pos = *head; for(;cur->next != NULL;cur=cur->next) { for(;pos->next!=tail;pos=pos->next) { if(pos->data>pos->next->data) { swap(&pos->data,&pos->next->data) } } tail = pos; } } }

将两个链表合并为一个有序链表

linklist *linklist_merge(linklist *head1,linklist *head2) { if(head1 == NULL) { return head2; } if(head2 == NULL) { return head1; } else { linklist *cur1 = head1; linklist *cur2 = head2; linklist *newhead = NULL; linklist *newtail = NULL; if(cur1->data<cur2->data) { newhead = newtail = cur1 cur1 = cur1->next; } else { newhead = newtail = cur2; cur2 = cur2->next; } while(cur1 != NULL &&cur2 != NULL) { if(cur1->data <= cur2->data) { newtail->next = cur1; newtail = newtail->next; cur1 = cur1->next; } else { newtail->next = cur2; newtail = newtail->next; cur2 = cur2->next; } } if(cur1 == NULL) { newtail->next = cur2; } else { newtail->next = cur1; } return newhead; } }

找到倒数第k个节点

linklist_size(linklist *head) { if(head == NULL) { return;//空 } else { size_t count = 0; linklist *cur = head; while(cur != NULL) { cur = cur->next; count++; } return count; } } linklist *linklist_findlastknode(linklist *head,size_t k) { if(head == NULL) { return NULL;//空 } if(k > linklist_size(head)) { return NULL;//超过了范围 } else { size_t i=linklist_size(head)-k; linklist *cur = head; for(;i>0;i--) { cur = cur->next; } return cur; } }

删除倒数第k个节点

void linklist_eraselastknode(linklist **head,size_t k) { if(*head == NULL) { return;//非法输入 } if(head == NULL) { return;//空 } if(k > linklist_size(head)) { return;//超范围 } else { linklist *pos = linklist_findlastknode(head,k); linklist_erase(head,pos); } }

判断链表是否带环，如果带环则返回入口点

linklist *linklist_getenter(linklist *head) { if(head == NULL) { return; } else { linklist *fast = head; linklist *slow = head; while(fast &&fast->next) { fast = fast->next->next; slow = slow->next; if(fast == slow) { linklist *meet = fast; linklist *cur = head; while(meet != cur) { cur = cur->next; meet = meet->next; } return meet; } } return NULL; } }

判断两个链表是否相交，如果相交就返回交点（不带环）

“` linklist *linklist_iscross(linklist *head1,linklist *head2) { if(head1 == NULL) { return NULL; } if(head2 == NULL) { return NULL; } else { linklist *cur1 = head1; linklist *cur2 = head2; while(cur1 != NULL) { cur1 = cur1->next; } while(cur2 != NULL) { cur2 = cur2->next; } if(cur1 == cur2) { size_t len = 0; len1 = linklist_size(head1); len2 = linklist_size(head2); linklist *pos1 = head1; linklist *pos2 = head2; if(len1-len2) { size_t len = len1-len2; for(;len>0;len–) { pos1 = pos1->next; } } else { size_t len = len2-len1; for(;len>0;len–) { pos2 = pos2->next; } } while (pos1 != pos2) { pos1 = pos1->next; pos2 = pos2->next; } return pos1; } return NULL; } }