当前位置：首页 → 问答吧 → 求助。正想跳槽去面试遇到的题目

求助。正想跳槽去面试遇到的题目

时间：2010-06-22

来源：互联网

如何不使用新节点倒置一个非循环单向链表？想了很久没想出来

作者: 输给钱的男人发布时间: 2010-06-22

有人会吗。。

作者: 输给钱的男人发布时间: 2010-06-22

这是“数据结构”的作业题啊，
goole “倒置单向链表”

作者: c/unix 发布时间: 2010-06-22

有答案？不能引入新的节点啊

作者: 输给钱的男人发布时间: 2010-06-22

不让使用新节点，让不让用新指针？

作者: 狗气球发布时间: 2010-06-22

最笨的办法，思路和冒泡相似，一个个的换。

作者: k8king 发布时间: 2010-06-22

我也不会。。。

作者: pandaiam 发布时间: 2010-06-22

呢地神哪，楼主你面的哪？

一个指针解决问题。

作者: zhaohongjian000 发布时间: 2010-06-22

QUOTE:

呢地神哪，楼主你面的哪？

一个指针解决问题。
zhaohongjian000 发表于 2010-06-22 15:38

不允许用新节点，允许用指针？

作者: asdmonster 发布时间: 2010-06-22

QUOTE:

不允许用新节点，允许用指针？
asdmonster 发表于 2010-06-22 15:52

不允许创建新节点是为了防止那种傻瓜式的倒置：每访问一个节点，就创建一个节点，然后将这个节点的next置上上个节点的地址，遍历完原先的节点后，就生成了一条新的倒置的链表啊。

题目的原意应该是这样，没你想的复杂，所以用一个指针，递归置换就ok。

作者: doofy 发布时间: 2010-06-22

贴个测试代码~~

include <stdio.h>
#include <stdlib.h>
struct node_t {
struct node_t *next;
int index;
};
struct node_t *malloc_node(int index)
{
struct node_t *pnode = malloc(sizeof(struct node_t));
pnode->index = index;
return pnode;
}
struct node_t *init_node(int num)
{
int i = 0;
struct node_t *node_head = malloc(sizeof(struct node_t));
struct node_t *pnode;
struct node_t *pre_node = node_head;
for(; i < num; i++) {
pnode = malloc_node(i);
pre_node->next = pnode;
pre_node = pnode;
}
pnode->next = NULL;
return node_head;
}
void dump_node_list(struct node_t *phead)
{
struct node_t *p = phead;
while(p->next) {
p = p->next;
printf("index: %d\n", p->index);
}
}
struct node_t *convert_node(struct node_t *pre_node, struct node_t *pnode)
{
struct node_t *tmp = pnode->next;
struct node_t *last = NULL;
if(pnode->next) {
last = convert_node(pnode, pnode->next);
tmp->next = pnode;
pnode->next = pre_node;
} else {
pnode->next = pre_node;
last = pnode;
}
return last;
}
void convert(struct node_t *phead)
{
struct node_t *last = NULL;
last = convert_node(NULL, phead->next);
phead->next = last;
}
int main()
{
struct node_t *phead = init_node(10);
dump_node_list(phead);
convert(phead);
dump_node_list(phead);
return 0;
}

复制代码

作者: doofy 发布时间: 2010-06-22

#include <stdio.h>
struct node
{
struct node *next;
int data;
};
int main()
{
int a[6];
int i;
struct node *node;
struct node *root;
struct node *tmp;
void *b;
void *c;
void *d;
int flag;
flag=0;
b=NULL;
c=NULL;
tmp = NULL;
root=NULL;
node=NULL;
for ( i=0;i<6;i++ )
{
a[i]=i;
}
/*创建六个节点开始*/
for ( i=0;i<6;i++ )
{
node=malloc(sizeof(struct node));
if ( 0==i )
{
root=node;
node->next=NULL;
tmp=root;
node->data=a[i];
continue;
}
node->next=NULL;
node->data=a[i];
((struct node *)tmp)->next = node;
node = NULL;
tmp=tmp->next;
}
/*创建六个节点结束*/
tmp=root;
i=0;
/*打印节点*/
while ( NULL!=tmp )
{
fprintf(stderr,"%d ",tmp->data);
tmp=tmp->next;
i++;
}
i=i-3;
fprintf(stderr,"\n");
/*倒置节点开始*/
b=root->next->next;
root->next->next=root;
c=root->next;
root->next->next->next=NULL;
root=b;
while ( flag!=i )
{
flag++;
root=b;
b=root->next;
root->next=c;
c=root;
}
root=b;
root->next=c;
tmp=root;
/*倒置节点结束*/
while ( NULL!=tmp)
{
fprintf(stderr,"%d ",tmp->data);
tmp=tmp->next;
}
fprintf(stderr,"\n");
tmp=root;
while ( NULL!=tmp)
{
d=tmp->next;
free(tmp);
tmp=d;
}
tmp = NULL;
root = NULL;
}

复制代码

大家帮忙看看我写的这个对不对！

作者: kanhfshiys 发布时间: 2010-06-22

网上搜的
      typedef struct node
{
         int data;
         struct node *link;
}NODE;

void reverse(NODE head)
{
         NODE temp = null;
         NODE p = head->link;
         head->link = null;// 头结点变为尾结点

         while(p!=null)
         {
            temp = p->link;
            p->link = head;// 当前结点指针倒置
            head = p;
            p = temp;
         }
}

作者: kmindg 发布时间: 2010-06-22

节点和指针是一样的吗？一个是用户定义大小未知，一个4字节的变量

作者: ydfgic 发布时间: 2010-06-22

。。。递归的做法是有问题的，会栈溢出的的。

作者: benjiam 发布时间: 2010-06-22

QUOTE:

不允许用新节点，允许用指针？
asdmonster 发表于 2010-06-22 15:52

节点是节点，指针是指针....

作者: zhaohongjian000 发布时间: 2010-06-22

void reverse( struct node *head )
{
if( head==NULL )
return;
struct node *pre, *cur, *nex;
pre = head;
cur = pre->next;

while( cur )
{
nex = cur->next;

cur->next = pre;

pre = cur;
cur = nex;
}

head->next = NULL;
head = pre;

return;
}

作者: mgqw 发布时间: 2010-06-22

单向链表这种数据结构，我是从来不用的，链条断裂死的很惨，而且还很不好查。

作者: 没本发布时间: 2010-06-22