当前位置: 代码迷 >> Web前端 >> 链表的一些常见笔试面试有关问题总结及代码
  详细解决方案

链表的一些常见笔试面试有关问题总结及代码

热度:376   发布时间:2012-06-26 10:04:13.0
链表的一些常见笔试面试问题总结及代码
链表的一些常见笔试面试问题总结及代码

先什么也不说,假设链表节点的数据结构为:

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节点的值(int型):";
cin >> head->data;
if (n == 1)
{
   return head;
}
node* p = head;
for (unsigned int i = 1; i < n; i++)
{
   node* tmp = new node;
   tmp->next = 0;
   cout << "请输入第" << i+1 << "个节点的值(int):";
   cin >> 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 < k; i++)
{
   p = p->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=1
node* 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 < n; i++)
   {
    q = q->next;
   }
   p->next = q;
}
return;
}

void destroy(node* head)
{
//销毁链表
if (loop(head))
{
   node *q = findLoopPlace(head);
   while (head != q)
   {
    node* p = head;
    head = head->next;
    delete p;
   }
   head = head->next;
   q->next = NULL;
   destroy(head);
}
else
{
   while (head != NULL)
   {
    node* p = head;
    head = head->next;
    delete p;
   }
}
}
  相关解决方案