Chinaunix首页 | 论坛 | 博客
  • 博客访问: 577657
  • 博文数量: 158
  • 博客积分: 4380
  • 博客等级: 上校
  • 技术积分: 2356
  • 用 户 组: 普通用户
  • 注册时间: 2006-09-21 10:45
文章分类

全部博文(158)

文章存档

2012年(158)

我的朋友

分类: C/C++

2012-11-19 10:39:33

水精灵的blog上看到趋势的一道考题"线性链表的倒序排列",如果是双向链表就太简单了不值得一提,难就难在"怎样将单链表倒序排列",这道题很常见,我当初也思考过,得出的结论是"更改单链表节点的指针方向,而不是调换其数据",完整算法如下:
for( Node *pre=0,*next; head&&(next=head->next,head->next=pre,next); pre=head,head=next );
抛砖引玉,看看有没有更好的算法,或更简洁的代码。

完整的测试代码如下:
#include
#include
using namespace std;

struct Node
{
    int value;
    Node* next;
    Node( int v ) : value(v),next(0) {}
};
Node* head = 0;

void Pout( void )
{
    for( Node* p=head; p; p=p->next )
        cout << p->value << ',';
    cout << "END"<< endl;
}

void Reverse( void )
{
    // 等同于for( Node *pre=0,*next; head&&(next=head->next,head->next=pre,next); pre=head,head=next )
    for( register Node *phead=head,*pre=0,*next; head; )
    {
        next = phead->next;
        phead->next = pre;
        if( !next )
        {
            head = phead;
            break;
        }
        pre = phead;
        phead = next;
    }
}

int main( void )
{
    head = 0;
    head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    Pout();
    Reverse();
    Pout();
    // 内存释放与本主题无关

    system("PAUSE");
    return 0;
}



------------ 2006-06-21日更新 ------------

#include
using namespace std;

struct Node
{
    int value;
    Node* next;

    Node( int v, Node* p ) : value(v), next(p) {}
};

void reverse( Node*& p )
{
    Node* t = 0;
    for( ; p ; )
    {
        Node* _t = t;
        t = p;
        p = p->next;
        t->next = _t;
    }
    p = t;
}

ostream& operator<<( ostream& os, const Node* p )
{
    os << '[';
    if( p ) { os << p->value; p=p->next; }
    for( ; p; p=p->next ) os << ',' << p->value;
    os << ']';
    return os;
}

int main(void)
{
    Node* p = new Node( 0, new Node( 1, new Node( 2, new Node( 3, new Node( 4, new Node( 5, 0 ) ) ) ) ) );

    cout << p << endl;
    reverse( p );
    cout << p << endl;

    return 0;
}

输出:
[0,1,2,3,4,5]
[5,4,3,2,1,0]

阅读(2962) | 评论(16) | 转发(0) |
给主人留下些什么吧!~~

网友评论2012-11-19 10:46:48

sdsd
一句话: 从头部插入

网友评论2012-11-19 10:46:36

babam
link reverse(link x)
{ link t,y=x,r=0;
while(y!=0)
{t=y->next;y->next=r;r=y;y=t;}
return r;
}

网友评论2012-11-19 10:46:23

hbn
void ListReverse(CLinkedList *pList)
{
    TListNode *pPrior = NULL;
    TListNode *pCurrent = NULL;
    TListNode *tmpCurrent = pList ->pHead;

    pList ->pTail = pList ->pHead;          /* 尾指针指向头结点 */
    while(NULL != tmpCurrent)
    {                    &n

网友评论2012-11-19 10:46:04

weljin
晕!刚链接进来!
++++++++++++++++++++++++++++++++++++
for( Node *pre=0,*next; head&&(next=head->next,head->next=pre,next); pre=head,head=next )
++++++++++++++++++++++++++++++++++++
这是什么来的?说实话,我暂时还看不明白!级数相差太大了!

++++++++++++++++++++++++++++++++++++
   for( register Node *phead=head,*pre=0,*next; head; )
    {
        next = phead->next;
  &

网友评论2012-11-19 10:45:46

周星星
^_^ 幸会,幸会!