关于链表的总结（C++循环实现）

0.目录

1.链表的基本操作

• 1.1 结点定义
• 1.2 创建链表
• 1.3 销毁链表
• 1.4 打印链表
• 1.5 获取链表长度

2.结点的基本操作

• 2.1 删除结点
• 2.2 查找结点

3.面试题

• 3.1 反转链表
• 3.2 合并两个单向排序链表
• 3.3 查找两个链表的第一个公共结点
• 3.4 删除排序链表中重复的结点

1.链表的基本操作

1.1 结点定义

#include <iostream>

using namespace std;

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

1.2 创建链表

Node* createLinkedList(int data[], int len)
{
    Node* ret = NULL;
    Node* slider = NULL;

    for(int i=0; i<len; i++)
    {
        Node* n = new Node();

        n->value = data[i];
        n->next = NULL;

        if( slider == NULL )
        {
            slider = n;
            ret = n;
        }
        else
        {
            slider->next = n;
            slider = n;
        }
    }

    return ret;
}

1.3 销毁链表

void destroyLinkedList(Node* list)
{
    while( list )
    {
        Node* del = list;

        list = list->next;

        delete del;
    }
}

1.4 打印链表

void printLinkedList(Node* list)
{
    while( list )
    {
        cout << list->value << "->";

        list = list->next;
    }

    cout << "NULL" << endl;
}

1.5 获取链表长度

int getListLength(Node* list)
{
    int ret = 0;

    while( list )
    {
        ret++;
        list = list->next;
    }

    return ret;
}

测试：

int main()
{
    int a[] = {1, 5, 3, 2, 4};

    Node* list1 = createLinkedList(a, 5);
    printLinkedList(list1);
    cout << getListLength(list1) << endl;
    destroyLinkedList(list1);
    cout << endl;

    Node* list2 = createLinkedList(NULL, 0);
    printLinkedList(list2);
    cout << getListLength(list2) << endl;
    destroyLinkedList(list2);
    cout << endl;

    int b[] = {6};
    Node* list3 = createLinkedList(b, 1);
    printLinkedList(list3);
    cout << getListLength(list3) << endl;
    destroyLinkedList(list3);

    return 0;
}

运行结果为：

1->5->3->2->4->NULL
5

NULL
0

6->NULL
1

2.结点的基本操作

2.1 删除结点

Node* deleteNode(Node* list, int value)
{
    Node* head = list;
    Node* slider = NULL;

    while( head && (head->value == value) )
    {
        slider = head;
        head = head->next;
        slider = NULL;
    }

    Node* ret = head;

    while( ret )
    {
        slider = ret->next;

        if( slider && (slider->value == value) )
        {
            ret->next = slider->next;
            slider = NULL;
        }
        else
        {
            ret = ret->next;
        }
    }

    return head;
}

测试：

int main()
{
    int a[] = {1, 2, 3, 2, 5};

    Node* list1 = createLinkedList(a, 5);
    printLinkedList(list1);
    printLinkedList(deleteNode(list1, 2));
    destroyLinkedList(list1);
    cout << endl;

    Node* list2 = createLinkedList(NULL, 0);
    printLinkedList(list2);
    printLinkedList(deleteNode(list2, 2));
    destroyLinkedList(list2);
    cout << endl;

    int b[] = {2, 2, 2, 2, 2};
    Node* list3 = createLinkedList(b, 5);
    printLinkedList(list3);
    printLinkedList(deleteNode(list3, 2));
    destroyLinkedList(list3);
    cout << endl;

    int c[] = {1};
    Node* list4 = createLinkedList(c, 1);
    printLinkedList(list4);
    printLinkedList(deleteNode(list4, 2));
    destroyLinkedList(list4);

    return 0;
}

运行结果为：

1->2->3->2->5->NULL
1->3->5->NULL

NULL
NULL

2->2->2->2->2->NULL
NULL

1->NULL
1->NULL

2.2 查找结点

Node* findNode(Node* list, int value)
{
    Node* ret = NULL;
    Node* slider = list;

    while( slider )
    {
        if( slider->value == value )
        {
            ret = slider;
            break;
        }
        else
        {
            slider = slider->next;
        }
    }

    return ret;
}

3.面试题

3.1 反转链表

Node* reverseLinkedList(Node* list)
{
    Node* ret = NULL;
    Node* slider = list;
    Node* next = NULL;

    while( slider )
    {
        next = slider->next;
        slider->next = ret;
        ret = slider;
        slider = next;
    }

    return ret;
}

测试：

int main()
{
    int a[] = {1, 5, 3, 2, 4};

    Node* list1 = createLinkedList(a, 5);
    printLinkedList(list1);
    printLinkedList(reverseLinkedList(list1));
    destroyLinkedList(list1);
    cout << endl;

    Node* list2 = createLinkedList(NULL, 0);
    printLinkedList(list2);
    printLinkedList(reverseLinkedList(list2));
    destroyLinkedList(list2);
    cout << endl;

    int b[] = {6};
    Node* list3 = createLinkedList(b, 1);
    printLinkedList(list3);
    printLinkedList(reverseLinkedList(list3));
    destroyLinkedList(list3);

    return 0;
}

运行结果为：

1->5->3->2->4->NULL
4->2->3->5->1->NULL

NULL
NULL

6->NULL
6->NULL

3.2 合并两个单向排序链表

Node* mergeLinkedList(Node* list1, Node* list2)
{
    Node* ret = NULL;

    if( list1 == NULL )
    {
        ret = list2;
    }
    else if( list2 == NULL )
    {
        ret = list1;
    }
    else
    {
        if( list1->value < list2->value )
        {
            ret = list1;
            list1 = list1->next;
        }
        else
        {
            ret = list2;
            list2 = list2->next;
        }

        Node* slider = ret;

        while( list1 && list2 )
        {
            if( list1->value < list2->value )
            {
                slider->next = list1;
                list1 = list1->next;
            }
            else
            {
                slider->next = list2;
                list2 = list2->next;
            }

            slider = slider->next;
        }

        if( list1 == NULL )
        {
            slider->next = list2;
        }
        else if( list2 == NULL )
        {
            slider->next = list1;
        }
    }

    return ret;
}

测试：

int main()
{
    int a[] = {1, 2, 4, 6, 8};

    Node* list1 = createLinkedList(a, 5);
    printLinkedList(list1);

    int b[] = {2, 2, 3, 3, 7};
    Node* list2 = createLinkedList(b, 5);
    printLinkedList(list2);

    Node* list3 = mergeLinkedList(list1, list2);
    printLinkedList(list3);
    destroyLinkedList(list3);

    return 0;
}

运行结果为：

1->2->4->6->8->NULL
2->2->3->3->7->NULL
1->2->2->2->3->3->4->6->7->8->NULL

3.3 查找两个链表的第一个公共结点

Node* findFirstCommonNode(Node* list1, Node* list2)
{
    int len1 = getListLength(list1);
    int len2 = getListLength(list2);
    Node* ret = NULL;

    if( len1 > len2 )
    {
        for(int i=0; i<(len1-len2); i++)
        {
            list1 = list1->next;
        }
    }
    else
    {
        for(int i=0; i<(len2-len1); i++)
        {
            list2 = list2->next;
        }
    }

    while( list1 )
    {
        if( list1 == list2 )
        {
            ret = list1;
            break;
        }
        else
        {
            list1 = list1->next;
            list2 = list2->next;
        }
    }

    return ret;
}

测试：

int main()
{
    int a[] = {1, 2, 3};
    Node* list1 = createLinkedList(a, 3);

    int b[] = {4, 5};
    Node* list2 = createLinkedList(b, 2);

    int c[] = {6, 7};
    Node* list3 = createLinkedList(c, 2);

    Node* ret = NULL;

    ret = list1;
    while( ret->next )
    {
        ret = ret->next;
    }
    ret->next = list3;

    ret = list2;
    while( ret->next )
    {
        ret = ret->next;
    }
    ret->next = list3;

    printLinkedList(list1);
    printLinkedList(list2);

    ret = findFirstCommonNode(list1, list2);
    printLinkedList(ret);

    return 0;
}

运行结果为：

1->2->3->6->7->NULL
4->5->6->7->NULL
6->7->NULL

3.4 删除排序链表中重复的结点

Node* deleteDuplicationNode(Node* list)
{
    Node* head = list;
    Node* toDel = NULL;
    Node* end = NULL;

    // 处理头结点重复的情况
    while( head && head->next && (head->value == head->next->value) )
    {
        end = head;
        // 找到最后一个与头结点重复的结点
        while( end && end->next && (end->value == end->next->value) )
        {
            end = end->next;
        }
        // 删除中间与头结点重复的结点
        while( head != end )
        {
            toDel = head;
            head = head->next;
            toDel = NULL;
        }
        // 删除最后一个与头结点重复的结点
        toDel = head;
        head = head->next;
        toDel = NULL;
    }

    Node* ret = head;
    Node* slider = NULL;

    while( ret && ret->next )
    {
        slider = ret->next;

        // 处理中间结点重复的情况
        while( slider && slider->next && (slider->value == slider->next->value) )
        {
            end = slider;
            // 找到最后一个与中间结点重复的结点
            while( end && end->next && (end->value == end->next->value) )
            {
                end = end->next;
            }
            // 删除中间与中间结点重复的结点
            while( slider != end )
            {
                toDel = slider;
                slider = slider->next;
                toDel = NULL;
            }
            // 删除最后一个与中间结点重复的结点
            toDel = slider;
            slider = slider->next;
            ret->next = slider;
            toDel = NULL;
        }

        if( ret->next == slider )
        {
            ret = ret->next;
        }
        else
        {
            ret->next = slider;
        }
    }

    return head;
}

测试：

int main()
{
    int a[] = {1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};

    Node* list1 = createLinkedList(a, 12);
    printLinkedList(list1);
    printLinkedList(deleteDuplicationNode(list1));
    destroyLinkedList(list1);
    cout << endl;

    Node* list2 = createLinkedList(NULL, 0);
    printLinkedList(list2);
    printLinkedList(deleteDuplicationNode(list2));
    destroyLinkedList(list2);
    cout << endl;

    int b[] = {2, 3, 3, 3, 4, 4, 5, 6, 6, 7};
    Node* list3 = createLinkedList(b, 10);
    printLinkedList(list3);
    printLinkedList(deleteDuplicationNode(list3));
    destroyLinkedList(list3);
    cout << endl;

    int c[] = {1};
    Node* list4 = createLinkedList(c, 1);
    printLinkedList(list4);
    printLinkedList(deleteDuplicationNode(list4));
    destroyLinkedList(list4);

    return 0;
}

运行结果为：

1->1->1->2->2->2->3->4->4->4->5->5->NULL
3->NULL

NULL
NULL

2->3->3->3->4->4->5->6->6->7->NULL
2->5->7->NULL

1->NULL
1->NULL