單鏈表是筆試以及面試手寫代碼中常考的數據結構之一。下面實現了單鏈表的常見操作：創建單鏈表、刪除節點、打印單鏈表（包括正向打印以及逆向打印）、反轉單鏈表、找出單鏈表的倒數第K個節點、合并兩個有序單鏈表等操作。

代碼（C++）：

//筆試面試單鏈表常用操作編程實現#include <iostream>#include <stack>#include <cstdlib>using namespace std;//單鏈表節點數據結構定義typedef struct link_node_s{    int m_val;    struct link_node_s *next;}link_node_t,*link_list_t;//函數:創建單鏈表(頭插法)link_list_t create_linklist(int *a,int n);//函數:打印單鏈表(從頭到尾)void print_linklist(link_list_t head);//函數:打印單鏈表(從尾到頭)void print_linklist_reverse(link_list_t head);//函數:新建鏈表節點link_list_t creart_linknode(int val);//函數:刪除鏈表中的某一個節點(前提條件:該節點一定存在)//性能要求:在O(1)時間復雜度內實現void delete_node_exist(link_list_t *head,link_list_t node_deleted);//函數:刪除鏈表中數據值等于給定值的節點void delete_node(link_list_t *head,int val);//函數:獲得鏈表中的倒數第K個節點link_list_t get_kth_node(link_list_t head,int k);//函數:反轉鏈表link_list_t reverse_linklist(link_list_t head);//函數:合并兩個已排序的鏈表(遞歸方法實現)link_list_t merge_linklist_recursive(link_list_t head1,link_list_t head2);int main(){    const int num1 = 8;    const int num2 = 10;    int *a = new int[num1];    int *b = new int[num2];    int *a_sorted = new int[num1];    int *b_sorted = new int[num2];    srand(1);    for(int i = 0;i < num1;++i){        *(a + i) = rand() % 100;        *(a_sorted + i) = 50 - i * 2 + 8;    }    for(int i = 0;i < num2;++i){        *(b + i) = rand() % 200;        *(b_sorted + i) = 50 - i * 4 + 1;    }    cout << "**********創建鏈表測試**********" << endl;    link_list_t list1 = create_linklist(a,num1);    link_list_t list2 = create_linklist(b,num2);    link_list_t list_sorted1 = create_linklist(a_sorted,num1);    link_list_t list_sorted2 = create_linklist(b_sorted,num2);    cout << "**********輸出鏈表測試(正向輸出)**********" << endl;    cout << "鏈表1:" << endl;    print_linklist(list1);    cout << "鏈表1(已序):" << endl;    print_linklist(list_sorted1);    cout << "鏈表2(已序):" << endl;    print_linklist(list_sorted2);    cout << "**********輸出鏈表測試(逆向輸出)**********" << endl;    print_linklist_reverse(list1);    cout << "**********獲取鏈表的倒數第K個節點測試**********" << endl;    int k = 3;    link_list_t kth_node = get_kth_node(list1,k);    if(NULL == kth_node)        cout << "鏈表中倒數第" << k << "個節點不存在" << endl;    else        cout << "鏈表中倒數第" << k <<"個節點是: " <<kth_node->m_val << endl;     k = 8;    kth_node = get_kth_node(list1,k);    if(NULL == kth_node)        cout << "鏈表中倒數第" << k << "個節點不存在" << endl;    else        cout << "鏈表中倒數第" << k <<"個節點是: " <<kth_node->m_val << endl;     k = 11;    kth_node = get_kth_node(list1,k);    if(NULL == kth_node)        cout << "鏈表中倒數第" << k << "個節點不存在" << endl;    else        cout << "鏈表中倒數第" << k <<"個節點是: " <<kth_node->m_val << endl;     cout << "**********刪除鏈表中一定存在的節點測試(輸入參數是要刪除的節點指針)**********" << endl;    link_list_t node_deleted = list1;    while(node_deleted->m_val != *(a + 4))        node_deleted = node_deleted->next;    cout << "刪除節點" << *(a + 4) << "之后的單鏈表:" << endl;    delete_node_exist(&list1,node_deleted);    print_linklist(list1);    node_deleted = list1;    while(node_deleted->m_val != *(a + 6))        node_deleted = node_deleted->next;    cout << "刪除節點" << *(a + 6) << "之后的單鏈表:" << endl;    delete_node_exist(&list1,node_deleted);    print_linklist(list1);    cout << "**********刪除鏈表中值等于給定值的節點測試(不一定存在,輸入參數是int型值)**********" << endl;    const int val_deleted = 22;    delete_node(&list1,val_deleted);    cout << "刪除值等于" << val_deleted << "之后的鏈表:" << endl;    print_linklist(list1);    cout << "**********合并鏈表測試**********" << endl;    link_list_t merge_list_head = merge_linklist_recursive(list_sorted1,list_sorted2);    print_linklist(merge_list_head);    cout << "**********逆轉鏈表測試**********" << endl;    link_list_t head_reverse = reverse_linklist(merge_list_head);    cout << "逆轉之后的鏈表:" << endl;    cout << "頭節點:" << head_reverse->m_val << endl;    print_linklist(head_reverse);    return 0;}//函數:創建單鏈表(頭插法)link_list_t create_linklist(int *a,int n){    link_list_t head = NULL;    if(NULL == a || 0 == n)        return NULL;    for(int i = 0;i < n;++i){        link_list_t new_node = creart_linknode(*(a + i));        if(NULL == head){            head = new_node;        }        else{            new_node->next = head;            head = new_node;        }    }    return head;}//函數:新建鏈表節點link_list_t creart_linknode(int val){    link_list_t node = new link_node_t;    node->m_val = val;    node->next = NULL;    return node;}//函數:打印單鏈表void print_linklist(link_list_t head){    link_list_t node = head;    cout << "正向輸出單鏈表" << endl;    while(node != NULL){        cout << node->m_val << " ";        node = node->next;    }    cout << endl;    return;}//函數:打印單鏈表(從尾到頭)void print_linklist_reverse(link_list_t head){    stack<int> node_stack;    link_list_t node = head;    while(node != NULL){        node_stack.push(node->m_val);        node = node->next;    }    cout << "逆向輸出單鏈表" << endl;    while(!node_stack.empty()){        cout << node_stack.top() << " ";        node_stack.pop();    }    cout << endl;    return;}//函數:刪除鏈表中的某一個節點(前提條件:該節點一定存在)//性能要求:在O(1)時間復雜度內實現void delete_node_exist(link_list_t *head,link_list_t node_deleted){    //算法思想:    //通過拷貝要刪除節點的后繼節點的內容覆蓋要刪除節點的內容,然后刪除要刪除節點的后繼節點即可    //要考慮的特殊情況是:要刪除的節點是鏈表尾部節點,仍然需要遍歷鏈表    if(NULL == head || NULL == node_deleted)        return;    //要刪除的節點不是尾節點    if(node_deleted->next != NULL){        link_list_t next_node = node_deleted->next;        node_deleted->m_val = next_node->m_val;        node_deleted->next = next_node->next;        delete next_node;        next_node = NULL;    }    //鏈表中只有一個節點    else if(*head == node_deleted){        delete node_deleted;        node_deleted = NULL;        *head = NULL;    }    //要刪除的節點是尾節點    else{        link_list_t node = *head;        while(node->next != node_deleted)            node = node->next;        node->next = node_deleted->next;        delete node_deleted;        node_deleted = NULL;    }    return;}//函數:獲得鏈表中的倒數第K個節點link_list_t get_kth_node(link_list_t head,int k){    //性能:只需遍歷鏈表一遍即可    //算法思想:設置兩個指針,一個指向鏈表頭部,一個指向第k個節點,然后兩個指針同時向后移動,當第二個指針指向鏈表的尾節點時,第一個指針指向的節點便是倒數第K個節點    //注意代碼的魯棒性,防止程序的崩潰    if(NULL == head || k <= 0)        return NULL;    //設置兩個指針    link_list_t p1 = head,p2 = head;    int i = 0;    //第二個指針向前走k-1步    while(i < k - 1 && p2->next != NULL){        p2 = p2->next;        ++i;    }    //注意鏈表中總節點數小于K的情況    if(i != k - 1 && NULL == p2->next)        return NULL;    //兩個指針同時向后前進    while(p2->next != NULL){        p1 = p1->next;        p2 = p2->next;    }    return p1;}//函數:反轉鏈表//返回值:反轉之后的鏈表頭節點link_list_t reverse_linklist(link_list_t head){    //鏈表為空或者只有一個節點    if(NULL == head || NULL == head->next)        return head;    link_list_t prev_node = NULL,next_node,cur_node = head,head_reverse;    while(cur_node != NULL){        next_node = cur_node->next;        if(NULL == next_node)            head_reverse = cur_node;//原鏈表尾節點即逆轉后鏈表的頭節點        cur_node->next = prev_node;        prev_node = cur_node;        cur_node = next_node;    }    return head_reverse;}//函數:刪除鏈表中數據值等于給定值的節點void delete_node(link_list_t *head,int val){    if(NULL == head){        cout << "Delete node failed :The node to be delete not exist!" << endl;        return;    }    if(val == (*head)->m_val){        link_list_t node = *head;        *head = (*head)->next;        delete node;        return;    }    //首先判斷該節點是否存在鏈表中    link_list_t node = *head;    while(node->next != NULL){        if(val == node->next->m_val)            break;        node = node->next;    }    //存在滿足條件的節點    if(node->next != NULL){        link_list_t node_delete = node->next;        node->next = node_delete->next;        delete node_delete;    }    else        cout << "刪除失敗:鏈表中不存在值等于" << val << "的節點" << endl;    return;}//函數:合并兩個已排序的鏈表(遞歸方法實現)link_list_t merge_linklist_recursive(link_list_t head1,link_list_t head2){    if(NULL == head1)        return head2;    else if(NULL == head2)        return head1;    link_list_t merge_head = NULL;    if(head1->m_val < head2->m_val){        merge_head = head1;        merge_head->next = merge_linklist_recursive(head1->next,head2);    }    else{        merge_head = head2;        merge_head->next = merge_linklist_recursive(head1,head2->next);    }    return merge_head;}測試平臺：WIn8+Ubuntu12.04+Vim+G++：
運行結果：