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 阅读(419) 评论(0)  编辑  收藏 所属分类: C/C++

只有注册用户登录后才能发表评论。
网站导航: