【经典算法】:链表翻转

朱雀 2022-09-23 10:49 139阅读 0赞

比如说一个链表先是这样， 40 5 0 60 反过来就应该是 60 0 5 40

函数如下：

static void reverse(struct node** head_ref){      //用于翻转，把所有的对应关系都反过来
        struct node* prev = NULL;
        struct node* current = *head_ref;
        struct node* next;
        while(current!=NULL){
            next = current->next;
            current->next = prev;     //倒过来指
            prev = current;
            current = next;  //用来将循环往后拖
        }
        *head_ref = prev;   //代表着最后一个
    }

传进去的参数是链表头  
原理就是把链表都反过来指，最后一个指向倒数第二个，方法是通过上述的三个数据结构完成的，next是为了遍历链表，而current和prev是为了表明指向的地点  
**注意的是：while循环里面第二三句绝对不能换**

给出完整的程序：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    struct node{
        int data;
        struct node* next;
    };
    void push(struct node** head_ref,int new_data){
        struct node* new_node = (struct node*) malloc(sizeof(struct node));
        new_node->data = new_data;
        new_node->next = (*head_ref);
        (*head_ref) = new_node;
    }
    static void reverse(struct node** head_ref){      //用于翻转，把所有的对应关系都反过来
        struct node* prev = NULL;
        struct node* current = *head_ref;
        struct node* next;
        while(current!=NULL){
            next = current->next;
    
            current->next = prev;     //倒过来指
            prev = current;
            current = next;  //用来将循环往后拖
        }
        *head_ref = prev;   //代表着最后一个
    }
    
    void printList(struct node *head)
    
        {
    
            struct node *temp = head;
    
            while(temp != NULL)
    
            {
    
                printf("%d ", temp->data);
    
                temp = temp->next;
    
            }
    
        }
    int main(){
        struct node* head = NULL;
        push(&head,20);
        push(&head,4);
        push(&head,15);
        push(&head,85);
        push(&head,60);
        push(&head,100);
        printList(head);
        reverse(&head);
        cout<<endl<<"翻转后的结果"<<endl;
        printList(head);
        return 0;
    }

# 买一赠一，赠上求链表长度，链表长度函数 #

void find(struct node *head,int data){
        struct node *temp = head;
        while(temp!=NULL){
            if(temp->data==data){
                cout<<"已经找到了"<<endl;
                return ;
            }
            temp = temp->next;
        }
        cout<<"没有找到"<<endl;
    }
    
    int GetLength(struct node *head){
        int count = 0;
        struct node *temp = head;
        while(temp!=NULL){
            count++;
            temp = temp->next;
        }
        return count;
    }