剑指Offer

剑指Offer - 九度1518 - 反转链表
2013-11-30 03:09

题目描述：

输入一个链表，反转链表后，输出链表的所有元素。
(hint : 请务必使用链表)

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(0<=n<=1000)：代表将要输入的链表的个数。
输入的第二行包含n个整数t(0<=t<=1000000)：代表链表元素。

输出：

对应每个测试案例，
以此输出链表反转后的元素，如没有元素则输出NULL。

样例输入：

5
1 2 3 4 5
0

样例输出：

5 4 3 2 1
NULL

题意分析：
　　翻转链表也是经典的链表题了，仔细写都能写出来，不过要严格杜绝new、delete的使用。我曾经喜欢偷懒new一个头节点指向链表头，这样后面反转链表的代码会稍微简化一点。new和delete的问题在于new和delete的操作代价太高，如果函数经常被调用，性能缺陷就会迅速暴露出来。改天要学习一下new和delete的实现机制，明白一次new操作到底有多“贵”。
　　时间复杂度O(n)，空间复杂度O(1)。

// 651941    zhuli19901106    1518    Accepted    点击此处查看所有case的执行结果    1024KB    1226B    160MS
// 201311152146
#include <cstdio>
using namespace std;

struct Node{
    int val;
    struct Node *next;
    Node(int _val): val(_val), next(NULL){}
};

Node *reverse_list(Node *head)
{
    Node *root, *tail;
    
    if(head == NULL){
        return NULL;
    }
    
    root = new Node(0);
    while(head != NULL){
        tail = head->next;
        head->next = root->next;
        root->next = head;
        head = tail;
    }
    head = root->next;
    delete root;
    return head;
}

int main()
{
    Node *head, *tail, *root;
    int i, n, tmp;
    
    while(scanf("%d", &n) == 1){
        if(n <= 0){
            printf("NULL
");
            continue;
        }
        root = new Node(0);
        tail = root;
        for(i = 0; i < n; ++i){
            scanf("%d", &tmp);
            tail->next = new Node(tmp);
            tail = tail->next;
        }
        head = root->next;
        head = reverse_list(head);
        root->next = head;
        printf("%d", head->val);
        tail = head->next;
        while(tail != NULL){
            printf(" %d", tail->val);
            tail = tail->next;
        }
        printf("
");
        
        tail = root;
        while(tail != NULL){
            head = tail->next;
            delete tail;
            tail = head;
        }
    }
    
    return 0;
}