不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

一道华为面试题

楼主shzwfq（静苑）2006-03-24 20:18:47 在 C/C++ / C++ 语言提问

将一个单链表反序,只有一个链表头节点head,还有两个指向节点元素类型的指针p和q,不许申请新的节点及指针变量什么的.用c或c++实现算法.

我这道题没有作出来,比较菜哦,祝大家好运!! 问题点数：20、回复次数：26Top

1 楼citywanderer2005（流浪狗）回复于 2006-03-24 20:32:56 得分 5

int MyList::Reverse()
{
ListNode *ptr = _ptrFront;
ListNode *ptrpre = 0;

_ptrFront = _ptrEnd;
_ptrEnd = ptr;
while(ptr!=_ptrFront)
{
ListNode *temp = ptr->Next();
ptr->Next(ptrpre);
ptrpre = ptr;
ptr = temp;
}
_ptrFront->Next(ptrpre);
return 0;
}Top

2 楼llf_hust（）回复于 2006-03-24 20:33:36 得分 5

void InvertLinkedList( LinkList &L )
{
LinkList p,s;
// 逆置头指针L所指链表
p = L; L = NULL; // 设逆置后的链表的初态为空表
while ( p ) { // p 为待逆置链表的头指针
s = p; p = p->next; // 从 p 所指链表中删除第一个结点(s 结点)
s->next = L; L = s; // 将 s 结点插入到逆置表的表头
}
}Top

3 楼PieroLsl（斑马王子）回复于 2006-03-24 20:38:53 得分 5

p=head->next;q=p->next;head=q->next;p->next=NULL;
do
{
q->next=p;
p=q;
q=head;
head=head->next;
}while(head);

令P指向节点1，Q指向节点2，Head指向节点3，由于P转换后为尾节点，所以P－＞Next指向NULL
循环移动，直到Head为NULLTop

4 楼citywanderer2005（流浪狗）回复于 2006-03-24 20:39:45 得分 5

哦，只有一个head，改一下：
int MyList::Reverse()
{
ListNode *ptr = _ptrFront;
ListNode *ptrpre = 0;

//_ptrFront = _ptrEnd;
//_ptrEnd = ptr;
while(ptr!=NULL)
{
ListNode *temp = ptr->Next();
ptr->Next(ptrpre);
ptrpre = ptr;
ptr = temp;
}
//_ptrFront->Next(ptrpre);
_ptrFront = ptrpre;
return 0;
}Top

5 楼citywanderer2005（流浪狗）回复于 2006-03-24 20:46:29 得分 0

晕，没有别的指针，再改一下：
int MyList::Reverse()
{
ListNode *ptr = _ptrFront;
ListNode *ptrpre = 0;

//_ptrFront = _ptrEnd;
//_ptrEnd = ptr;
while(ptr!=NULL)
{
_ptrFront = ptr->Next();
ptr->Next(ptrpre);
ptrpre = ptr;
ptr = _ptrFront;

}
_ptrFront = ptrpre;
return 0;
}Top

6 楼citywanderer2005（流浪狗）回复于 2006-03-24 20:47:11 得分 0

不好意思啊，楼主Top

7 楼plamlover（火麒麟）回复于 2006-03-24 21:14:30 得分 0

规定时间不~~~~Top

8 楼yiyo2025（HenryKong）回复于 2006-03-24 22:00:29 得分 0

完整的例子，运行成功：

#include <iostream.h>

struct A
{
int m_value;
A *next;
};

A *Reverse(A *head)
{
A *p, *q;
if (head->next == NULL || head->next->next == NULL)
return head;

p = head->next;
q = p->next;
p->next = head;
head->next = NULL;
while (q != NULL)
{
head = p;
p = q;
q = q->next;
p->next = head;
}
return p;
}

int main(){
A array[5];

for(int i=0; i<5; i++)
{
array[i].m_value = i;
if (i == 4)
array[i].next = NULL;
else
array[i].next = &array[i+1];
}

A *head = array;

head = Reverse(head);

while (head != NULL)
{
cout<<head->m_value<<endl;
head = head->next;
}

return 0;
}

Top

9 楼gjianpro（#ifndef _DEBUG）回复于 2006-03-24 22:12:55 得分 0

for(Node *pre=0,*next; head&&(next=head->next,head->next=pre,next);Top

10 楼vsfan（窘）回复于 2006-03-24 23:08:37 得分 0

不是吧
感觉上很简单的题目。。。
while (!head)
{
p = head;
q = head->next;
head = head->next;
q->next = p;
}Top

11 楼BeginnerCpp（禅）回复于 2006-03-24 23:18:12 得分 0

递归，

递归是优雅的，可惜是不敢随便滥用的。

reverse(T* t)
{
if(NULL == t->nextPtr)
{ return t->value; }
else
{
reverse(t);
}

return t->value;
}Top

12 楼BeginnerCpp（禅）回复于 2006-03-24 23:35:27 得分 0

晕倒，看错题目了。

Top

13 楼linli2006（考研TOBEORNOTTOBE）回复于 2006-03-25 01:51:49 得分 0

在一本教材里头的习题里有出现Top

14 楼Lusoel（口哨）回复于 2006-03-25 06:44:28 得分 0

三个指针够啊!
先把Q和Head指向表尾结点,
P指向表头.
while(p != Head)
{
q->Next = p;
p = p->Next;
q->Next = NULL;
}
Top

15 楼zhejiang9（千万别忘了结帖!^_^!!）回复于 2006-03-25 10:25:31 得分 0

yiyo2025(EricKong)
你写的这个函数有个很明显的BUG哦
if (head->next == NULL || head->next->next == NULL)
return head;
？？？
这样当链表只有两个接结点的时候，第三个结点为空，直接返回头指针，根本没改变两个结点的顺序！
我帮你改了一下，呵呵

A *Reverse(A *head)
{
A *p1,*p2;
p1=head;
if(head->next==NULL)
return head;
p2=p1->next;
p1->next=NULL;
while(p2->next!=NULL)
{
head=p2->next;
p2->next=p1;
p1=p2;
p2=head;
}
p2->next=p1;
return p2;
}
Top

16 楼yiyo2025（HenryKong）回复于 2006-03-25 21:05:44 得分 0

确实疏忽了，多谢。Top

17 楼wangcw_jun（军）回复于 2006-03-25 21:30:06 得分 0

#include<iostream>
using namespace std;
node * insertnode(list *head)
{
node *p,*q;
p=null;
while(head!=null)
{
q=head->next;
head->next=p->next;
p->next=head;
head=q;
}
return q->next;
}
void main()
{
list *head;
node *p;
p=insert(head);
cout<<p;
}Top

18 楼Could（翻墙鹦鹉）回复于 2006-03-25 21:33:12 得分 0

把head后面的节点一个个地拿到head的前面来，
我想写一下自己的代码，然后再来学学大家的。Top

19 楼manplus（魅力加加）回复于 2006-03-25 22:56:19 得分 0

markTop

20 楼Could（翻墙鹦鹉）回复于 2006-03-25 23:08:48 得分 0

我做了，
跟前面某些人的思路一样的。
#include <iostream>
using namespace std;

class node
{
public:
node(int x):data(x),next(0){}
int data;
node* next;
};

node* ReversList(node* head)
{
node* p=0;
node* q=head;
while(head->next!=0)
{
p=head->next;
head->next=p->next;
p->next=q;
q=p;
}
return q;
}

int main()
{
node* head=new node(0);
node* tail=head;
for(int i=1;i<10;i++)
{
node* p=new node(i);
tail->next=p;
tail=p;
}
head=ReversList(head);
while(head->next!=0)
{
cout<<head->data<<endl;
head=head->next;
}
getchar();
return 0;
}Top

21 楼kendejihxx（冰赐&龙龙）回复于 2006-03-25 23:33:04 得分 0

mark 一下。我对C++不是很懂Top

22 楼iicup（双杯献酒）回复于 2006-03-26 15:51:00 得分 0

华为也出这种无聊题?Top

23 楼hu_cdut（古月）回复于 2006-03-27 08:48:28 得分 0

vsfan(窘):
你的算法错了!Top

24 楼plamlover（火麒麟）回复于 2006-03-28 12:51:05 得分 0

思考算法用了三分钟,写出完事程序用了近半个小时~~~太不熟了..
下面是本要的完事程序
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
char data;
struct node *link;
}node;
void creat(node *head) //创建一个链表
{
char t;
node *n;
head->link=NULL;
//head->data=0;
printf("please input link data ");
scanf("%c",&t);
while(t!='#')
{
n=(node *)malloc(sizeof(node));
n->data=t;
n->link=head->link;
head->link=n;
scanf("%c",&t);
}
}
void show(node head) //打印所有结点
{
node *p;
p=head.link;
while(p)
{
printf("%4c",p->data);
p=p->link;
}
}
void reverse(node *head) //题目中所需要的函数
{
node *p,*q;
p=head->link;
q=p->link;
while(q)
{
p->link=q->link;
q->link=head->link;
head->link=q;
q=p->link;
}
}
void main()
{
node head;
creat(&head);
show(head);
reverse(&head);
putchar('\n');
show(head);
}
Top

25 楼judely（蓝山|西堤岛|卡布奇诺）回复于 2006-03-30 10:48:54 得分 0

学习`~Top

26 楼wxiantong（）回复于 2006-03-30 20:47:36 得分 0

easy!!!
void reverse(T*head)
{
T*p=head,*q=head->next;
while(q)
{
head=q->next;
q->next=p;
p=q;
q=head;
}
head=p;
}Top