A Za, A Za, Fighting...

坚信:勤能补拙

带随机指针的链表复制

题目来源:
http://zhedahht.blog.163.com/blog/static/254111742010819104710337/

题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:

                struct ComplexNode

{

    int m_nValue;

    ComplexNode* m_pNext;

    ComplexNode* m_pSibling;

};


代码:
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

struct Node {
    
char value;

    
struct Node *next;
    
struct Node *random;
};

void test_print(struct Node *);

struct Node *
list_copy_with_random_pointer(
struct Node *head)
{
    
struct Node *tmp, *ptr, *ret;

    ptr 
= head;
    
while(ptr != NULL) {
        tmp 
= (struct Node *)malloc(sizeof(struct Node));
        tmp
->value = (ptr->value)-32/* from lowercase to uppercase, just for testing */
        tmp
->next = ptr->next;
        tmp
->random = NULL;

        ptr
->next = tmp;

        ptr 
= ptr->next->next;
    }

    ptr 
= head;
    
while(ptr != NULL) {
        ptr
->next->random = ptr->random==NULL ? NULL : ptr->random->next;

        ptr 
= ptr->next->next;
    }

    ptr 
= head;
    ret 
= (head==NULL ? NULL : (head->next));
    
while(ptr != NULL) {
        tmp 
= ptr->next;
        ptr
->next = ptr->next->next;
        tmp
->next = ptr->next==NULL ? NULL : ptr->next->next;

        ptr 
= ptr->next;
    }

    
return ret;
}

void
test_print(
struct Node *head)
{
    
while(head != NULL) {
        printf(
"%c: [%c, %c]\n", head->value, head->next==NULL?'-':head->next->value, head->random==NULL?'-':head->random->value);

        head 
= head->next;
    }
}

int
main(
int argc, char **argv)
{
    
struct Node d = {'d', NULL, NULL};
    
struct Node c = {'c'&d, NULL};
    
struct Node b = {'b'&c, NULL};
    
struct Node a = {'a'&b, NULL};
    a.random 
= &c;
    d.random 
= &b;

    test_print(
&a);

    
struct Node *copy = list_copy_with_random_pointer(&a);

    printf(
"\n\n");
    test_print(
&a);
    printf(
"\n\n");
    test_print(copy);

    
return 0;
}

posted on 2011-06-09 11:35 simplyzhao 阅读(364) 评论(0)  编辑 收藏 引用 所属分类: M_面试题集锦


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜