The NoteBook of EricKong

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  611 Posts :: 1 Stories :: 190 Comments :: 0 Trackbacks
#include <iostream>
typedef 
struct __node {
    
int value;
    __node
* next;
}
 NODE, *PNODE;

PNODE reverse(PNODE head) 
{
    
if (!head) {
        
return head;
    }

    PNODE curNode 
= head;
    PNODE nextNode 
= head->next;
    head
->next = NULL;
    
while (nextNode) {

        PNODE afterNextNode 
= nextNode->next;
        nextNode
->next = curNode;
        curNode 
= nextNode;
        nextNode 
= afterNextNode;
    }

    
return curNode;
}

PNODE reverse_recursionA(PNODE head) 
{
    
if (head == NULL || head->next == NULL) {

        
return head;
    }

    PNODE temp 
= reverse_recursionA(head->next);
    head
->next = temp->next;
    temp
->next = head;
    
return head;
}

PNODE reverse_recursionB(PNODE head) 
{
    
if (head == NULL || head->next == NULL) {

        
return head;
    }

    PNODE temp 
= reverse_recursionB(head->next);
    head
->next->next = head;
    
return temp;
}

PNODE reverse_recursionC(PNODE cur, PNODE pre) 
{
    
if (NULL == cur) {

        
return pre;
    }

    PNODE temp 
= cur->next;
    cur
->next = pre;
    
return reverse_recursionC(temp, cur);
}

void printList(PNODE head) {
    PNODE curNode 
= head;
    
while (curNode) {

        std::cout 
<< curNode->value << ' ' << std::flush;

        curNode 
= curNode->next;
    }

    std::cout 
<< std::endl;
}

int main() {
    PNODE head 
= new NODE();
    head
->value = 0;
    head
->next = NULL;
    PNODE tail 
= head;
    
for (int index = 1; index != 100++index) {

        PNODE newNode 
= new NODE();
        newNode
->value = index;
        newNode
->next = head;
        head 
= newNode;
    }

    std::cout 
<< "Original: " << std::endl;
    printList(head);
    head 
= reverse(head);
    std::cout 
<< "After reverse: " << std::endl;
    printList(head);
    tail 
= head;
    head 
= reverse_recursionB(head);
    tail
->next = NULL;
    std::cout 
<< "After one reverse_recrusionB: " << std::endl;
    printList(head);
    reverse_recursionA(head);
    PNODE temp 
= head;
    head 
= tail;
    tail 
= temp;
    std::cout 
<< "After reverse_recursionA: " << std::endl;
    printList(head);
    tail 
= head;
    head 
= reverse_recursionC(head, NULL);
    std::cout 
<< "After reverse_recursionC: " << std::endl;
    printList(head);

    PNODE curNode 
= head;
    
while (curNode) {

        PNODE temp 
= curNode->next;

        delete curNode;

        curNode 
= temp;
    }

    
return 0;
}
posted on 2012-05-21 16:07 Eric_jiang 阅读(412) 评论(0)  编辑  收藏 所属分类: C/C++

只有注册用户登录后才能发表评论。


网站导航: