首页 > 代码库 > 单链表反转

单链表反转

1, 非递归方式

List* ListRevert(List* list)
{
    List* head = NULL;  //new list head
    List* temp = NULL;
    while (list!= NULL){  //each time pick up a node from the old list, and add as the new list head
        temp = list->next;
        list->next = head;
        head = list;
        list = temp;
    }
    return head;
}

2, 递归方式

//make sure call the function like this: head=ListRevert_Recursive(head, NULL);

List* ListRevert_Recursive(List* list, List* pre)
{
    List* temp = list;
    if (list == NULL ){
        return list;
    }
    else if (list->next == NULL){
        list->next = pre;
        return list;
    }
    List* newhead = ListRevert_Recursive(list->next, list);  //recursive until we find the list head, and save to newhead
    list->next = pre;
    return newhead;
}

单链表反转