链表的基本操作和题

链表节点的插入和删除

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

//末尾插入节点
void AddToTail(Node** head, int value) { //head是一个指向指针的指针
    Node *Node_new = new Node();
    Node_new->value = value;
    Node_new->next = nullptr;

    if(*head == nullptr) {
        *head = Node_new;
    }
    Node *Node_temp = *head;

    while(Node_temp->next != nullptr) {
        Node_temp = Node_temp->next;
    }
    Node_temp->next = Node_new;
}

void RemoveNode(Node** head, int value) { //删除节点
    if(*head == nullptr || head == nullptr)
        return ;
    Node* Node_delete = nullptr;
    if(*head->value = value) {
        Node_delete = *head;
        *head = (*head)->next;
    }
    else {
        Node* Node_temp = *head;
        while(Node_temp->next != nullptr && Node_temp->next->value != value) {
            Node_temp = Node_temp->next;
        }
        if(Node_temp->next != nullptr && Node_temp->next->value == value) {
            Node_delete = Node_temp->next;
            Node_temp->next = Node_temp->next->next;
        }
    }
    if(Node_delete != nullptr) {
        delete Node_delete;
        Node_delete = nullptr;
    }
}

---

从尾到头打印链表

void travel(Node* head) {
    if(head != nullptr) {
        if(head->next != nullptr) {
            travel(head->next);
        }
        printf("%d\n",head->value);
    }
}

---

在O(1)时间内删除链表节点

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

void DeleteNode(Node** head, Node* ToBedelete) { //在O(1)时间内删除节点
    if(!head || !ToBedelete) {
        return ;
    }
    if(ToBedelete->next != nullptr) { //删除的不是尾节点
        Node* Node_temp = ToBedelete->next;
        ToBedelete->value = ToBedelete->next->value;
        ToBedelete->next = Node_temp->next;
        delete Node_temp;
        Node_temp = nullptr;
    }
    else if(*head == ToBedelete){ //要删除的是头节点,且只有一个节点
        delete ToBedelete;
        ToBedelete = nullptr;
        *head = nullptr;
    }
    else { //删除的是尾节点
        Node* Node_temp = *head;
        while(Node_temp->next->value != ToBedelete->value) {
            Node_temp = Node_temp->next;
        }
        Node_temp->next = nullptr;
        delete ToBedelete;
        ToBedelete = nullptr;
    }
}

---

删除重复的节点

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

void DeleteNode(Node** head) { //删除重复的节点
    if(*head == nullptr || head == nullptr) {
        return ;
    }

    Node* Node_pre = nullptr;
    Node* Node_temp = *head;
    while(Node_temp != nullptr) {
        bool NeedDelete = false;
        Node* Node_next =Node_temp->next;
        if( Node_temp != nullptr && Node_temp->value == Node_next->value) {
            NeedDelete = true;
        }
        else {
            Node_pre = Node_temp;
            Node_temp = Node_next;
        }

        if(NeedDelete == true) {
            int value = Node_temp->value;
            Node* ToBeDel = Node_temp;
            while(ToBeDel != nullptr && ToBeDel->value == value) {
                Node_next = ToBeDel->next;
                delete ToBeDel;
                ToBeDel = nullptr;
                ToBeDel = Node_next;
            }
            if(Node_pre == nullptr){
                *head = ToBeDel;
            }
            else {
                Node_pre->next = Node_next;
            }
            Node_temp = Node_next;
        }
    }
}

---

链表中倒数第k个节点

struct Node {
    int value;
    Node* next;
};
// 注意空指针，k==0时，链表倒数第k个节点，时间复杂度O(n),只循环一次
Node* FindKthToTail(Node* head, unsigned int k) { 
    if(head==nullptr || k < 1) {
        return nullptr;
    }
    Node* Node_ahead = head;
    Node* Node_behind = nullptr;
    for(unsigned int i = 0; i < k - 1; i++) {
        if(Node_ahead->next == nullptr) {
            return nullptr;
        }
        Node_ahead = Node_ahead->next;
    }
    Node_behind = head;
    while(Node_ahead->next != nullptr) {
        Node_ahead = Node_ahead->next;
        Node_behind = Node_behind;
    }
    return Node_behind;
}

---

#用前序和后序构建一颗二叉树#

#include <iostream>

using namespace std;

struct BinaryTreeNode {
    int vaule;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

BinaryTreeNode* construct(int* preorder, int* inorder, int length) {

    if(preorder == nullptr || inorder == nullptr || length <= 0) 
        return nullptr;
    else 
        return constructcore(preorder, preorder+length-1, inorder, inorder+length-1);
}

BinaryTreeNode* constructcore(int pre_start, int pre_end, int in_start, int in_end) {

    BinaryTreeNode* root = new BinaryTreeNode();
    root->vaule = pre_start[0];
    root->left = root->right = nullptr;

    if(pre_start == pre_end) {
        if(in_end == in_start && *in_start == *pre_end)
            return root;
        else 
            throw exception("invalid input");
    }

    int* in_search_root = in_start;
    while(in_search_root <= in_end && root->vaule != *in_search_root)
        ++in_search_root;
    if(in_search_root > in_end) {
        throw exception("invalid input");
    }
    int left_length = in_search_root - in_start;
    if(left_length > 0)
        root->left = constructcore(pre_start+1,pre_start+left_length,in_start, in_search_root -1);
    if(in_end-in_search_root > 0)
        root->right = constructcore(pre_start+left_length+1,pre_end,in_search_root+1,in_end);
    return root;

}