链表处理

1.创建链表

#include <cstdio>

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

node *create(int arr[], int n) {
    node *p, *cur, *head;//cur当前结点，head头结点
    head = new node;
    head->next = NULL;//头结点不需要数据域
    cur = head;
    for (int i = 0; i < n; i++) {
        p = new node;
        p->data = arr[i];
        p->next = NULL;
        cur->next = p;
        cur = p;
    }
    return head;
}

int main() {
    int arr[5] = {5, 3, 6, 1, 2};
    node *link = create(arr, 5);
    link = link->next;//从第一个结点开始有数据域
    while (link != NULL) {
        printf("%d", link->data);
        link = link->next;
    }
    return 0;
}

2.查找元素

//返回链表中元素x的个数
int search(node *head, int x) {
    int count = 0;
    node *p = head->next;
    while (p != NULL) {
        if (p->data == x) {
            count++;
        }
        p = p->next;
    }
    return count;
}

3.插入元素

//将x插入链表第pos个位置上
void insert(node *head, int pos, int x) {
    node *p = head;
    for (int i = 0; i < pos - 1; i++) {
        p = p->next;
    }
    node *q = new node;
    q->data = x;
    q->next = p->next;
    p->next = q;
}

4.删除元素

//删除所有数据域为x的结点
void del(node *head, int x) {
    node *p = head->next;
    node *pre = head;//pre始终保存p的前驱
    while (p != NULL) {
        if (p->data == x) {
            pre->next = p->next;
            delete (p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

5.静态链表

struct Node {
    int data;
    int next;
} node[1000];

1074 Reversing Linked List

1032 Sharing

1052 Linked List Sorting

1097 Deduplication on a Linked List