Chinaunix首页 | 论坛 | 博客
  • 博客访问: 933445
  • 博文数量: 153
  • 博客积分: 4195
  • 博客等级: 上校
  • 技术积分: 2631
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-22 11:32
文章存档

2012年(7)

2010年(35)

2009年(111)

分类:

2009-08-04 22:20:16

 链表的几个经典问题
2008-03-27 21:21:01
 标签:算法 链表   [推送到技术圈]

版权声明:原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。http://bluefish.blog.51cto.com/214870/68462
下面是几个关于链表的非常经典的问题与实现,是在《程序员面试攻略》中看到的,由于实在是太经典了,所以忍不住在这里贴下。

    问题1:给定一个单项链表,设计一个时间优化并且时间优化的算法,找出该链表的倒数第m个元素。当m=0时,返回链表的最后一个元素。
    [分析:用双指针来实现,两指针间隔m。同步移动两指针,当前一个指针为该链表tail时,后一个指针就为要找的元素]
Element * FindMToLastElement( Element * head, int m)
{
    Element * current, * mBehind;
    int i;
    current = head;

    for( i = 0; i < m; i++)
    {
        if(current->next)
        {
            current = current->next;
        }

        else
        {
            return NULL;
        }

    }


    mBehind = head;
    while(current->next)
    {
        current = current->next;
        mBehind = mBehind->next;
    }


    return mBehind;
}


    问题2:从一个标准的双向链表开始。假定除了next指针和previous指针之外,每个元素保存了一个child指针,它可能指向一个独立的双向链表,也可能为空。这些子链表又可能有一个或多个子链表,如此下去,得到了一个多层次的数据结构。将这个链表展平,使得所有节点都出现在一个一层的双向链表中。每个节点定义如下:
typedef struct Node{
    struct Node * next;
    struct Node * prev;
    struct Node * child;
    int value;
}
Node;
    [分析:从第一层链表头开始遍历链表,如果有第二层链表,则将其放到第一层链表尾。这样其实第一层链表尾一直在往后移动,原来的第一层在遍历完后就可以直接遍历第二层了,依此类推就可以完成题目要求,前提要有一个指向尾指针的指针]
void FlattenList( Node * head, Node ** tail)
{
    Node * curNode = head;
    while( curNode )
    {
        if(curNode->child)
        {
            Append(curNode->child, tail);
        }

        curNode = curNode->next;
    }

}


void Append( Node * child, Node ** tail)
{
    Node * curNode;
    (*tail)->next = child;
    child-prev = *tail;

    for(curNode = child; curNode->next; curNode = curNode->next)
    {
    }


    *tail = curNode;
}


    问题3:编写一个函数,接受链表的头指针作为参数,确定该链表是循环的还是非循环的。如果链表是非循环的,函数返回false;如果是循环的,函数返回true。不能以任何方式修改该链表。
    [分析:用双指针实现,一个用step=1前进,一个用step=2前进。看两个指针是否能相遇]
bool DetermineTermination( Node * head)
{
    Node * fast, * slow;
    fast = slow = head;
    while(true)
    {
        if(!fast || !fast->next)
        {
            return false;
        }

        else if(fast == slow || fast->next == slow)
        {
            return true;
        }

        else
        {
            slow = slow->next;
            fast = fast->next->next;
        }

    }

}

本文出自 “bluefish” 博客,请务必保留此出处http://bluefish.blog.51cto.com/214870/68462

本文出自 51CTO.COM技术博客
阅读(928) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~