About
RSS

Bit Focus


单链表 给我翻过来

Posted at Dec 21 2011 - 04:59:53

下面是一个简单的单链表节点结构
struct node {
    int value;
    struct node* next;
};
那么如何将这个链表反转过来呢?
void reverse(struct node* head);

下面采用递归的方式实现, 废话少说, 直接上代码
struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}
上面的实现假定传入的 head 不会是空节点. 如果要检测, 可以加入一个判断
void reverse(struct node* head)
{
    if (NULL != head)
        *_reverse(head) = NULL;
}

下面来验证一下吧
#include <stdio.h>

struct node {
    int value;
    struct node* next;
};

void reverse(struct node* head);

void print_list(struct node const* head);

int main(void)
{
    struct node a = { 0, NULL },
                b = { 1, &a },
                c = { 2, &b }; // c(2) -> b(1) -> a(0) -> NULL
    print_list(&c);
    reverse(&c); //    changed to a(0) -> b(1) -> c(2) -> NULL
    print_list(&a);
    return 0;
}

void print_list(struct node const* head)
{
    printf("[");
    for (; NULL != head; head = head->next) {
        printf(" %d", head->value);
    }
    printf(" ]\n");
}

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

Post tags:   C  Algorithm  Data Structure

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site