C语言链表类面试题.docx
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;
}
