单链表的基本操作

来源：www.rxwcv.cn

链表的数据结构

struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

新建链表

带头结点

带头节点的链表：此种链表保存数据是从head->next开始的，head中并未保存有数据，访问时自然head->next开始，优点就是方便操作。

头插法

ListNode* createList() {
    ListNode* head = new ListNode(0);
    ListNode* node = head;
    vector<int> nums = { 1,2,3 };
    for (int i = 0; i < nums.size(); ++i) {
        ListNode * temp = new ListNode(nums[i]);
        temp->next = node->next;
        node->next = temp;
    }

    return head;
}

尾插法

ListNode* createList() {
    ListNode* head = new ListNode(0);
    ListNode* node = head;
    vector<int> nums = { 1,2,3 };
    for (int i = 0; i < nums.size(); ++i) {
        ListNode * temp = new ListNode(nums[i]);
        node->next = temp;
        node = temp;
    }
    node->next = nullptr;
    return head;
}

不带头结点

不带头节点的链表：此种链表的head即保存第一个数据，访问时从head开始。不利于删除或者添加指定位置数据的操作。

头插法

ListNode* createList() {
    ListNode* head = nullptr;
    ListNode* node = nullptr;
    vector<int> nums = { 1,2,3 };
    for (int i = 0; i < nums.size(); ++i) {
        node = new ListNode(nums[i]);
        node->next = head;
        head = node;
    }

    return head;
}

尾插法

ListNode* createList() {
    ListNode* head = nullptr;
    ListNode* temp = head;
    ListNode* node = nullptr;
    vector<int> nums = { 1,2,3 };
    for (int i = 0; i < nums.size(); ++i) {
        node = new ListNode(nums[i]);
        if (!head) {
            head = node;
        }
        else {
            temp->next = node;
        }
        temp = node;
    }
    if (!temp) {
        temp->next = nullptr;
    }

    return head;
}

以下都使用带头结点的链表实现

打印链表

void printList(ListNode* head) {
    ListNode* node = head;
    while (node->next) {
        node = node->next;
        cout << node->val << "   ";
    }
    cout << endl;
}

指定位置插入节点

ListNode* insert(ListNode* head, int pos, int elem) {
    ListNode* temp = head;
    int i = 0;
    //首先找到插入节点的上一节点，即pos-1位置
    while ((temp->next != nullptr) && (i < pos - 1)) {
        temp = temp->next;
        ++i;
    }
    if (!temp || i > pos - 1) {
        cout << "Insert False!" << endl;
        return temp;
    }
    ListNode* node = new ListNode(elem);
    node->next = temp->next;
    temp->next = node;
    return head;
}

链表中查找某个节点

int searchNode(ListNode* head, int elem) {
    ListNode* node = head;
    int pos = 0;
    int i = 1;
    while (node->next) {
        node = node->next;
        if (elem == node->val) {
            pos = i;
            cout << "元素： " << elem << "  在链表中的位置是：" << pos << endl;
            return pos;
        }
        ++i;
    }
    cout << "search eoor!" << endl;
    return -1;
}

修改某节点的数据

ListNode* replaceNode(ListNode* head, int pos, int elem) {
    ListNode* node = head;
    node = node->next;
    for (int i = 1; i < pos; ++i) {
        node = node->next;
    }
    node->val = elem;
    return head;
}

获取链表长度

int sizeList(ListNode* head) {
    int size = 0;
    ListNode* node = head;
    while(node->next) {
        ++size;
        node = node->next;
    }
    cout << "链表的长度是： " << size << endl;
    return size;
}

判断链表是否为空

bool isEmptyList(ListNode* head) {
    if (!head) {
        cout << "链表为空！" << endl;
        return true;
    }
    cout << "链表不为空！" << endl;
    return false;
}

删除链表节点

ListNode* deleteNode(ListNode* head, int pos) {
    ListNode* node = head;
    int i = 0; 
    while (node->next && i < pos - 1) {
        node = node->next;
        ++i;
    }
    if (!node || i > pos - 1) {
        cout << "delete false!" << endl;
        return node;
    }
    ListNode* del = node->next;
    node->next = del->next;
    delete del;
    del = nullptr;
    return head;
}

清空链表

void clearList(ListNode* head) {
    ListNode* node = head;
    ListNode* temp;
    if (!head) {
        cout << "链表为空！" << endl;
    }
    while (node->next) {
        temp = node->next;
        delete node;
        node = temp;
    }
    delete node;
    delete temp;
    node = nullptr;
    temp = nullptr;
    head->next = nullptr;
    cout << "链表清空！" << endl;
}

链表销毁

void destoryList(ListNode* head) {

    if (!head) {
        cout << "链表为空！" << endl;
    }
    ListNode* node = nullptr;
    while (head->next) {
        node = head->next;
        delete head;
        head = node;
    }
    if (head) {
        delete head;
        head = nullptr;
    }
    cout << "链表销毁成功！" << endl;

}