常见面试题之链表操作_单链表有没有前驱

一、链表创建

链表主要有三种形式，包括单链表、双链表和循环链表。
单链表每个节点只包含一个后驱指针，双链表节点同时包含一个前驱指针和一个后驱指针，循环链表的尾节点的后驱指向头节点。
代码如下：

/*单链表节点结构*/
typedef struct NodeType
{
char elem;
NodeType*next;
}Node;

/*双链表节点结构*/
typedef struct DNodeType
{
char elem;
DNodeType*next;
DNodeType*prev;
}DNode;

/*
创建链表
*/
Node* CreateList(Node*head)
{
if(NULL== head)//分配头节点空间
head=(Node*)malloc(sizeof(Node)),
head->next=NULL;

Node*current=head ,*temp;
char ch;

while(1)
{
cout<<”\n input elem:”;
cin>>ch;
if(‘#’ == ch)/*#结束输入*/
break;
temp=(Node*) malloc (sizeof(Node) );
temp->elem=ch;
temp->next=NULL;
current->next=temp;/*当前节点的后驱指向新节点*/
current=temp;/*当前节点为链表尾节点*/

}

return head;
}



/*创建双链表*/
DNode* DoubleList(DNode*head)
{
if(NULL== head)//分配头节点空间
head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL , head->next=NULL;

DNode*current=head ,*temp;
char ch;

while(1)
{
cout<<”\n input elem:”;
cin>>ch;
if(‘#’ == ch)/*#结束输入*/
break;
temp=(DNode*) malloc (sizeof(DNode) );
temp->elem=ch;
temp->next=NULL;
current->next=temp;/*当前节点的后驱指向新节点*/
temp->prev=current;/*新节点的前驱指向当前节点*/
current=temp;/*当前节点为链表尾节点*/

}

return head;
}



/*创建循环链表*/
Node* CycleList(Node*head)
{
if(NULL== head)/*分配头节点空间*/
head=(Node*)malloc(sizeof(Node)),head->next=NULL;

Node*current=head ,*temp;
char ch;

while(1)
{
cout<<”\n input elem:”;
cin>>ch;
if(‘#’ == ch)/*#结束输入*/
break;
temp=(Node*) malloc (sizeof(Node) );
temp->elem=ch;
temp->next=NULL;
current->next=temp;/*当前节点的后驱指向新节点*/
current=temp;/*当前节点为链表尾节点*/

}
current->next=head;/*尾节点指向头节点*/
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

二、链表操作

包括单链表的增加节点、删除节点、输出链表等。

/*插入节点*/

Node*InsertNode(Node*head ,char elem)
{
if( NULL== head|| NULL== elem )
return head;

Node*current=head->next;/*当前节点*/
Node*prev=head;/*前驱节点*/
Node*temp;/*过渡节点*/

while(current)/*移动至尾节点*/
{
prev=current;
current=current->next;
}

temp=(Node*) malloc(sizeof(Node) );
temp->elem=elem;
temp->next=NULL;
prev->next=temp;/*尾节点的后驱指向新节点*/

return head;

}

/*
输出链表
*/
void PrintList(Node*head)
{
Node* current=head->next;
cout<<”\n List are:”;
while(NULL!= current)
{
if(NULL!= current->elem)
coutelem;
current=current->next;
}
cout<<”\n”;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

三、单链表逆置

单链表逆置在各公司的笔试题中比较常见，以下是其中一种实现。
算法描述：将链表中每一个节点插入到头结点之后。

单链表逆置/*单链表逆置*/
Node*ReverseList(Node*head)
{
if(NULL== head)
return head;
if(NULL== head->next)
return head;
if(NULL== head->next->next)
return head;

Node*curr=head->next;/*当前节点*/
head->next=NULL;
Node*temp;

while(curr)
{
temp=curr->next;/*暂存下一个节点*/
/*把当前节点插入到head节点后*/
curr->next=head->next;
head->next=curr;

curr=temp;/*移动至下一个节点*/
}

return head;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

四、求单链表中间节点

在笔试题中比较常见，通常题目描述是：给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间节点。
算法描述：设立两个指针p1,p2，p1每次移动1个节点位置，p2每次移动2个节点位置，当p2移动到尾节点时，p1指向中间节点。
代码如下：

/*求中间节点*/
Node* MiddleNode(Node*head)
{
if(NULL== head)
return head;
if(NULL== head->next)
return head->next;

Node*p1,*p2;
p1=head;
p2=head;

while(p2->next)
{
/*p2节点移动2个节点位置*/
p2=p2->next;
if(p2->next)/*判断p2后驱节点是否存在，存在则再移动一次*/
p2=p2->next;
/*p1节点移动1个节点位置*/
p1=p1->next;
}
return p1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

五、合并有序单链表

问题描述：合并2个有序单链表，合并后的链表也是排好序的。
算法描述：对链表A中的每一个节点元素，查找其在链表B中的插入位置，并在B中插入该元素。
代码如下：

/*合并有序单链表*/
Node* MergeList(Node* h1,Node* h2)
{
if(NULL== h1|| NULL== h2)
return h1;
if(NULL== h1->next )
return h2;
if(NULL== h2->next)
return h1;

Node* curr1,*curr2,*prev1,*temp;
prev1=h1;/*链表1的前驱节点*/
curr1=h1->next;/*链表1的当前节点*/
curr2=h2->next;/*链表2的当前节点*/
temp=h2;
while(curr2)
{
while(curr1&& curr1->elemelem)/*链表1指针移动至大或等于链表2当前元素的位置*/
prev1=curr1,curr1=curr1->next;

/*在链表1中插入链表2的当前元素*/
temp=curr2->next;/*暂存链表2的下一个节点*/
prev1->next=curr2;
curr2->next=curr1;

/*链表1移动至新节点*/
curr1=curr2;
/*链表2移动至下一个节点*/
curr2=temp;
}
return h1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

六、判断链表是否有环

判断链表是否有环即是判断链表是否为循环链表，算法较为简单，一次遍历判断尾指针是否指向头指针即可。
代码如下：

/*判断链表是否有环(循环链表)*/
bool IsCycleList(Node*head)
{
if(NULL== head)
return false;
if(NULL== head->next)
return false;
Node*current=head->next;
while(current)
{
if(head== current->next)
return true;
current=current->next;
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17