C语言链表类面试题.doc

本文由 太阳城（）提供struct node int data;struct node* next;创建单链表的程序为：struct node* create(unsigned int n)/创建长度为n的单链表assert(n 0);node* head;head = new node;head-next = NULL;cout head-data;if (n = 1) return head;node* p = head;for (unsigned int i = 1; i next = 0; cout 请输入第 i+1 tmp-data; p-next = tmp; p = tmp;return head;问题1：链表逆置思想为：head指针不断后移，指针反向即可，代码为：void reverse(node*& head)if (head != NULL & head-next != NULL) node* p = head; node* q = head-next; p-next = NULL; while (q-next != NULL) head = q-next; q-next = p; p = q; q = head; head-next = p;return;问题2：删除不知头结点链表的某个节点如果单向链表不知道头节点，一个指针指向其中的一个节点，问如何删除这个指针指向的节点？思想为：把这个节点的下一个节点的值复制给该节点，然后删除下一个节点即可。问题3：怎么判断链表中是否有环？思想为：设置两个指针，一个步长为1，另一个步长为2，依次后移，如果相遇且都不为空，则有环。与这个类似的问题包括：怎么快速检测出一个巨大的链表中的死链？或者如何找出一个单链表的中间节点？代码为：bool loop(node* head)bool flag = true;if (head = NULL) flag = false;node* one = head;node* two = head-next;if (two = NULL) flag = false;while (one != two) if (one != NULL) one = one-next; if (two != NULL) two = two-next; if (two = NULL) break; two = two-next; if (one = NULL | two = NULL) break; if (one = NULL | two = NULL) flag = false;return flag;问题4：如果一个单向链表，其中有环，怎么找出这个链表循环部分的第一个节点？思想为：假设该节点在x位置处，假设步长为1的指针和步长为2的指针相遇在x+z处，循环的长度为y，那么2(x+z)-(x+z)=k*y,那么当一个指针再从开始出后移时，另一个指针从相遇点开始后移时，这两个指针就会在循环开始处相遇。代码为：node* findLoopPlace(node* head, unsigned int* place = NULL)/查找循环的位置,place存储位置if (!loop(head) return NULL;node* one = head;node* two = head-next;unsigned int count = 1;while (one != two) one = one-next; two = two-next-next;one = head;while (one != two) if (count != 1) one = one-next; two = two-next; count+;*place = count;return one;问题5：如何查找链表中倒数第k个节点？思想为：两个指向头结点的指针，一个先向后移动k位，然后两个同时向后面移动直到一个节点到达链尾，前面一个指针的位置就是了。node* findLastK(node* head,unsigned int k)/查找单链表倒数第k个位置node* p = head;unsigned int count = 0;while (p != NULL) p = p-next; count+;if (count k) return NULL;p = head;node* q = head;for (unsigned int i = 0; i next;while (p != NULL) q = q-next; p = p-next;return q;问题6：编程序判断两个链表是否相交。这个问题的精彩解说请参见编程之美一书之编程判断两个链表是否相交，这里就不写了，该书的pdf文档在网上很好下。文章后面给了两个扩展问题：（1）如果链表可能有环，如何做判断？思想为：首先应该明白，只有一个链表有环的情况下是不会相交的，只有都有环或者都没有环的情况下才可能相交，都没有环的情况下最简便的方法就是判断链尾是否相交即可；都有环的情况下，分别找到环上的任一点，一个不动，另一个步进，即可判断是否相交。（2）如何求相交链表的第一个节点？应该为单链表情况思想为：方法一是先把任一个链表连成环，即从表尾接到表头，按照问题4的解法；方法二是计算两个链表的长度，而两个链表是按照尾部对齐的，那么从短链表的第一个位置从长链表的第长度差+1的位置依次比较指针值，相等的位置即是。相关程序包括：单链表中在某个位置插入环以及销毁链表等，代码如下：void insertCircle(node* head, unsigned int n)/在第n个位置形成环，记head为n=1node* p = head;node* q = head;unsigned int count = 1;while(p-next != NULL) p = p-next; count+;if (n = count) for (unsigned int i = 1; i next; p-next = q;return;void destroy(node* head)/销毁链表if (loop(head) node *q = findLoopPlace(head); while (head != q) node* p = head; head