面试遇到的一道链表题

前几天面试的时候被问到一道神奇的链表题,O(n)的复杂度求相交链表的交点,百思不得其解,最近终于在网上找到了一点思路,总结了一下相似的题目,祭奠我失败的面试T^T

首先是链表找中点的问题,一个简单的思路就是遍历一遍链表,得到链表长度l,然后再遍历链表,找到第l/2出的结点。不过,这道题还有另外一种思路:设两个指针,一个一次移动一个结点,另一个一次移动两个结点,当第二个到终点的时候,第一个的位置刚好是中点。

这两种算法看似复杂度一样,不过在实际应用中,双指针可以充分利用寄存器,达到更高的效率,而且,这种思想跟下面的题目很类似,所以记录下来,代码如下:

#include <stdio.h>
#include <stdlib.h>

#define MaxN 30

typedef struct node{
 int data;
 struct node* next;
}Node, *Linklist;

Linklist create_linklist();
Linklist find_middle(Linklist l);

int main()
{
 Linklist Head = create_linklist();
 Linklist middle = find_middle(Head);
 printf("%d\n", middle->data);
 return 0;
}

Linklist create_linklist()
{//创建链表
 Linklist Head = (Node *)malloc(sizeof(Node));
 Head->next = NULL;
 Linklist p = Head;
 int i = 0;
 for(i=1; i<=MaxN; ++i){
 p->next = (Node *)malloc(sizeof(Node));
 p = p->next;
 p->data = i;
 p->next = NULL;
 }
 return Head;
}

Linklist find_middle(Linklist l)
{
 Linklist p1=l, p2=l;
 while(p2 != NULL && p2->next != NULL){
 //p1每次向前一个,p2每次向前两个
 p1 = p1->next;
 p2 = p2->next->next;
 }
 return p1;
}

判断单链表是否有环,并找到环的入口。

设置三个指针p0,p1和p2,head是头指针p1每次往前访问一个结点,p2每次往前两个,当p2不能再访问下一个结点的时候说明链表无环,否则,p1会跟p2相遇。相遇之后,p0开始出发,每次往前一个结点,直到p0和p1相遇,这个时候p0和p1所在位置即为链表环的入口。具体证明这里不再给出。代码如下:

#include <stdio.h>
#include <stdlib.h>

#define MaxN 30
//链表最大长度

typedef struct node{
 int data;
 struct node* next;
}Node, *Linklist;

Linklist create_linklist();
Linklist find_entrance(Linklist l);

int main()
{
 Linklist Head = create_linklist();
 Linklist entrance = find_entrance(Head);
 if(entrance == NULL){
 printf("NULL\n");
 }else{
 printf("%d\n", entrance->data);
 }
 return 0;
}

Linklist create_linklist()
{//创建链表
 Linklist Head = (Node *)malloc(sizeof(Node));
 Head->next = NULL; //头结点
 Linklist p = Head;
 Linklist ent = Head; //ent为链表的环的入口

 int i = 0;
 for(i=1; i<=MaxN; ++i){
 p->next = (Node *)malloc(sizeof(Node));
 p = p->next;
 p->data = i;
 if(i == MaxN >> 1){
 ent = p; //该例中链表环的入口设在链表中部位置
 }
 p->next = NULL;
 }
 p->next = ent;
 return Head;
}

Linklist find_entrance(Linklist l)
{
 Linklist p0=l, p1=l, p2=l;
 while(1){
 //p1每次向前一个,p2每次向前两个
 if(p2 == NULL || p2->next == NULL){ //p2不能往前访问,说明无环
 return NULL;
 }
 p1 = p1->next;
 p2 = p2->next->next;
 if(p1 == p2){ //p1=p2 说明有环
 while(p0 != p1){
 p0 = p0->next;
 p1 = p1->next;
 }
 return p0;
 }
 }
 return NULL;
}

寻找交叉链表的交叉点。

从一个入口出发,一直访问到跟结点,然后将链表头尾相连,这样这道题就变成了寻找链表环的入口问题了,代码跟上面类似,不再给出。

发表评论

电子邮件地址不会被公开。 必填项已用*标注