链表

数据结构

定义

#include<iostream>
#include<cstdlib>
#include<assert.h>
#define ElemType int 
typedef struct node{
    ElemType val ;
    struct node* next ;
}LinkList ;

头插尾插创建链表

LinkList* create_List_Head(int n){
    LinkList* head = nullptr ;
    for(int i=0; i<n; i++){
        int v ;
        scanf("%d",&v);

        LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)) ;
        newNode->val = v ;
        newNode->next= head ;
        head = newNode ;
    }
    return head ;
}

LinkList* create_List_Tail(int n){
    LinkList* head ;
    LinkList* cur = head ;
    head->next = nullptr ;
    
    for(int i=0; i<n; i++){
        int v; 
        scanf("%d",&v) ;
        LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)) ;
        newNode->val = v ;
        newNode->next = nullptr ;
        head->next = newNode ;
        head = head->next ;
    }
    return cur->next ;
}

反转链表

LinkList* Reverse_LinkList(LinkList* head){
    /* 思想: 双指针*/
    LinkList* prev = nullptr ;
    LinkList* cur ; cur = head ;
    while(cur){
        LinkList* tmp = cur->next ;
        cur->next = prev ;
        prev = cur ;
        cur = tmp ;
    }
    return prev ;
}

LinkList* Reverse_LinkList_Recursion(LinkList* head){
    /* 递归解法 */
    //1. 递归结束条件
    if(head==nullptr || head->next == nullptr){
        return head ;
    }
    //2. 递归
    LinkList* cur = Reverse_LinkList_Recursion(head->next) ;
    head->next->next = head ;
    head->next = nullptr ;
    return cur ;
}

👋关于链表反转的推荐讲解 ：Leetcode

头删尾删

LinkList* Delete_Head(LinkList* head){
    if(head == nullptr){
        printf("head == nullptr !") ;
        exit(-1) ;
    }
    LinkList* cur = (LinkList*)malloc(sizeof(LinkList)) ;
    cur = head->next ;
    head->next = nullptr ;
    return cur ;
}

void Delete_Tail(LinkList* head){
    LinkList* cur = head ;
    while(cur->next->next) cur = cur->next ;
    cur->next = cur->next->next ;
}

增加结点

LinkList* ApplyNode(LinkList* head, int v){
    LinkList* cur = head ;
    while (cur->next) cur = cur->next ;
    LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)) ;
    cur->next = newNode ;
    newNode->val = v ;
    newNode->next = nullptr ;
    return newNode ;
}

打印

void Print(LinkList* head){
    if(head == nullptr){
        printf("head == nullptr !\n") ;
        exit(-1) ;
    }
    LinkList* cur = head ;
    while(cur){
        printf("cur->val = %d ",cur->val) ;
        printf("cur->next_add = %0X ",cur->next) ;
        cur = cur->next ;
        printf("\n") ;
    }
}

void Print_m_n(LinkList* head,int m, int n){
    int cnt ;
    LinkList* m_node = head ;
    LinkList* n_node = head ;
    LinkList* cur ;
    for(cnt=1;cnt<m;cnt++) m_node = m_node->next ;
    for(cnt=1;cnt<n;cnt++) n_node = n_node->next ;
    for(cur=m_node; cur!=n_node->next; cur = cur->next){
        printf("cur->val = %d \n",cur->val) ;
    }
}

销毁链表

void Destroy_List(LinkList** head){
	while(*head)
    {
        LinkList* next = (*head) -> next ;
        free(head) ;
        *head = next ;
    }
}

在函数中，如果需要修改指针变量本身的值，那么就需要传递指向指针变量的指针，即二级指针。

测试程序

// linklist.cpp
// 作为 .header 的验证程序，自己改注释
#include"linklist.h"
using namespace std ;

int main()
{
    LinkList h ;
    h.val = 2 ;
    h.next = nullptr ;
    // Print(&h) ;
    // // printf("Function \" Print \" TEST SUCCESS ! \n") ;

    // LinkList* p =  ApplyNode(&h,3) ;
    // printf("val = %d \n",p->val) ;    
    // Print(&h) ;
    // // printf("Function \" ApplyNode \" TEST SUCCESS ! \n") ;

    // Push_Tail(&h,4) ;
    // Print(&h);
    // // printf("Function \" Push_Tail \" TEST SUCCESS ! \n") ;
    
    // LinkList* q = Push_Head(&h,1) ;
    // Print(q) ;
    // // printf("Function \" Push_Head \" TEST SUCCESS ! \n") ;
    // // 1->2->3->4

    // Delete_Tail(q) ;
    // Print(q) ;
    // // printf("Function \" Delete_Tail \" TEST SUCCESS ! \n") ;
    // // 1->2->3

    // LinkList* m = Delete_Head(q) ;
    // Print(m) ;
    // // printf("Function \" Delete_Head \" TEST SUCCESS ! \n") ;
    // int s = Search(m,2) ;
    // printf("s = %d\n",s) ;

    // Destroy_List(&m) ;
    // Print(m) ;
    // printf("------------------------");
    
    // LinkList* phead = create_List_Head(3) ;
    // Print(phead) ;
    
    LinkList* phead = create_List_Tail(3) ;
    Print(phead) ;
    printf("------------------------\n");
    // LinkList* res = Reverse_LinkList_Recursion(phead) ;
    // Print(res) ;
    Print_m_n(phead,1,3);
    return EXIT_SUCCESS ;
}