链表（C++实现）

链表是一种线性的数据结构，其一个已有的链表中插入、删除一个链表结点的时间复杂度是O(n)。

以下为一个单链表C++简单的实现版本。

具体为：

头插法、尾插法，链表翻转的递归版和非递归版。

#include <cstdio>

struct Node
{
    int data ;
    Node *next ;
} ;

void Insert_Head( Node *&head , const int &val ) // 头插法
{
    Node *ptr = new Node() ;
    ptr->next = head ;
    ptr->data = val ;
    head = ptr ;
}

void Insert_Back( Node *&head , Node *&back ,const int &val ) // 尾插法
{
    Node *ptr = new Node() ;
    ptr->data = val ;
    ptr->next = NULL ;
    if ( head == NULL )
        head = back = ptr ;
    else {
        back->next = ptr ;
        back = ptr ;
    }
}

void Print( Node * const &head ) // 单链表的打印函数
{
    for ( Node *it = head ; it != NULL ; it = it ->next )
        printf("%d " , (*it).data );
    puts("") ;
}

void Reverse_not_Dfs( Node *&head ) // 翻转（非递归）
{
    if ( head == NULL )
        return ;
    Node *pre , *cur , *nxt ;
    pre = head ;
    cur = head->next ;
    while ( cur )
    {
        nxt = cur->next ;
        cur->next = pre ;
        pre = cur ;
        cur = nxt ;
    }
    head->next = NULL ;
    head = pre ;
}

Node* Reverse_Dfs( Node *p , Node *&head ) // 翻转（递归）
{
    if ( p->next == NULL )
    {
        head->next = NULL ;
        head = p ;
        return p ;
    }

    Node *tmp = Reverse_Dfs(p->next , head) ;
    tmp->next = p ;
    return p ;
}

int main()
{
    int n;
    while ( ~scanf("%d" , &n) )
    {
        Node *Fhead = NULL , *Bhead = NULL ,*back = NULL  ;
        int val , i ;
        for ( i = 0; i < n; i++ )
        {
            scanf("%d" , &val ) ;
            Insert_Head( Fhead , val ) ;
            Insert_Back( Bhead, back , val ) ;

        }

        printf( "Print Insert_head list : " ) ;
        Print( Fhead ) ;

        printf( "Print Insert_back list : ") ;
        Print(Bhead) ;

        printf( "The Insert_head list after Reverse : " ) ;
        Reverse_not_Dfs( Fhead ) ;
        Print( Fhead ) ;

        printf( "The Insert_back list after Reverse : " ) ;
        Reverse_Dfs(Bhead , Bhead) ;
        Print( Bhead ) ;
    }
    return 0 ;
}

简单的有序链表合并：

// 合并两个有序的链表 eg: 1 4 6 , 3 5 9 -> 1 3 4 5 6 9
Node* Merge_not_Dfs( Node *head1 , Node *head2 ) // 非递归版
{
    if ( head1 == NULL ) return head2 ;
    if ( head2 == NULL ) return head1 ;

    Node *head = NULL , *ptr1 = NULL , *ptr2 = NULL ;
    if ( head1->data < head2->data )
    {
        head = head1 ;
        ptr1 = head->next ;
        ptr2 = head2 ;
    }
    else
    {
        head = head2 ;
        ptr2 = head2->next ;
        ptr1 = head1 ;
    }

    Node *cur = head ;
    while ( ptr1 != NULL && ptr2 != NULL )
    {
        if ( ptr1->data <= ptr2->data )
        {
            cur->next = ptr1 ;
            cur = ptr1 ;
            ptr1 = ptr1->next ;
        }
        else
        {
            cur->next = ptr2 ;
            cur = ptr2 ;
            ptr2 = ptr2->next ;
        }
    }
    if ( ptr1 != NULL )
        cur->next = ptr1 ;
    if ( ptr2 != NULL )
        cur->next = ptr2 ;
    return head ;
}

Node* Merge_Dfs( Node *head1 , Node *head2 ) // 递归版
{
    if ( head1 == NULL ) return head2 ;
    if ( head2 == NULL ) return head1 ;

    Node *head =NULL ;
    if ( head1->data < head2->data )
    {
        head = head1 ;
        head->next = Merge_Dfs( head1->next , head2 ) ;
    }
    else
    {
        head = head2 ;
        head->next = Merge_Dfs( head1 , head2->next) ;
    }
    return head ;
}