This code provides a implement for the linkedList in C. It offers create, transverse, sort, inversion, append, insert, del and other functions of the linkedList.

Please notice that the sort method actually can be replaced by some advanced algorithm. YOU can replace them manually. This code only offers the simplest way to sort for popular and easy to understand.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
	int data;
	struct Node * pNext;
} Node, *pNode;

pNode createList(int length);
void transverseList(pNode pHead);
void inversion(pNode pHead);
void sort(pNode pHead);
int get(pNode pHead, int pos);
int maxL(pNode pHead);
int minL(pNode pHead);
int getLength(pNode pHead);
bool append(pNode pHead, int value);
bool insert(pNode pHead, int pos, int value);
bool del(pNode pHead, int pos);

int main(void) {
	pNode pHead;
	int length;

	printf("Please input how many nodes do you want to make: ");
	int len;
	scanf("%d", &len);
	pHead = createList(len);
	transverseList(pHead);
	length = getLength(pHead);
	printf("The minimum number is %d\n", minL(pHead));
	printf("The maximum number is %d\n", maxL(pHead));
	sort(pHead);
	transverseList(pHead);
	inversion(pHead);
	transverseList(pHead);

	return 0;
}

pNode createList(int length) {
	pNode head = (pNode)malloc(sizeof(Node));
	if (head == NULL) {
		printf("Failed to allocate memory!");
		exit(0);
	}
	pNode* pTemp = &(head->pNext);
	
	for (int i = 0; i < length; i++) {
		pNode ptr = (pNode)malloc(sizeof(Node));
		if (ptr == NULL) {
			printf("Failed to allocate memory!");
			exit(0);
		}
		printf("Please input data of %d node: ", i + 1);
		scanf("%d", &(ptr->data));
		ptr->pNext = NULL;
		*pTemp = ptr;
		pTemp = &(ptr->pNext);
	}
	return head;
}

void transverseList(pNode pHead) {
	pNode ptr = pHead;
	while (ptr->pNext != NULL) {
		printf("%d ", ptr->pNext->data);
		ptr = ptr->pNext;
	}
	printf("\n");
}

int getLength(pNode pHead) {
	int len = 0;
	pNode pTemp = pHead;
	while (pTemp->pNext != NULL) {
		len++;
 		pTemp = pTemp->pNext;
	}
	return len;
}

int minL(pNode pHead) {
	int min = pHead->pNext->data;
	pNode pTemp = pHead->pNext;
	while (pTemp != NULL) {
		if (pTemp->data < min)
			min = pTemp->data;
		pTemp = pTemp->pNext;
	}
	return min;
}

int maxL(pNode pHead) {
	int max = pHead->pNext->data;
	pNode pTemp = pHead->pNext;
	while (pTemp != NULL) {
		if (pTemp->data > max)
			max = pTemp->data;
		pTemp = pTemp->pNext;
	}
	return max;
}

bool append(pNode pHead, int value) {
	pNode pTemp = (pNode)malloc(sizeof(Node));
	pNode ptr = pHead;

	if (pTemp == NULL) {
		printf("Failed to allocate memory!");
		exit(0);
	}
	pTemp->data = value;
	pTemp->pNext = NULL;

	while (ptr->pNext != NULL) {
		ptr = ptr->pNext;
	}
	ptr->pNext = pTemp;

	return true;
}

bool del(pNode pHead, int pos) {
	pNode ptr = pHead;
	if (pos < 1 || pos > getLength(pHead)) {
		printf("Index out of bounds");
		exit(0);
	}
	for (int i = 0; i < pos - 1; i++) {
		ptr = ptr->pNext;
	}
	
	pNode r = ptr->pNext;
	ptr->pNext = ptr->pNext->pNext;
	free(r);

	return true;
}

bool insert(pNode pHead, int pos, int value) {
	if (pos < 1 || pos > getLength(pHead) + 1) {
		printf("Index out of bounds");
		exit(0);
	}
	pNode ptr = pHead;

	for (int i = 0; i < pos - 1; i++) {
		ptr = ptr->pNext;
	}
	pNode pTemp = ptr->pNext;

	ptr->pNext = (pNode)malloc(sizeof(Node));
	if (ptr->pNext == NULL) {
		printf("Failed to allocate memory!");
		exit(0);
	}
	
	ptr->pNext->data = value;
	ptr->pNext->pNext = pTemp;

	return true;
}

int get(pNode pHead, int pos) {
	if (pos < 1 || pos > getLength(pHead)) {
		printf("Index out of bounds");
		exit(0);
	}

	pNode ptr = pHead;

	for (int i = 0; i < pos; i++) {
		ptr = ptr->pNext;
	}

	return ptr->data;
}

void sort(pNode pHead) {
	int len = getLength(pHead);
	pNode ptr;
	int min;
	pNode pos;
	
	for (int i = 0; i < len; i++) {
		ptr = pHead->pNext;
		for (int m = 0; m < i; m++)
			ptr = ptr->pNext;
		min = ptr->data;
		pos = ptr;
		for (int k = i; k < len; k++) {
			if (ptr->data < min) {
				min = ptr->data;
				pos = ptr;
			}
			ptr = ptr->pNext;
		}
		ptr = pHead->pNext;
		for (int m = 0; m < i; m++)
			ptr = ptr->pNext;
		pos->data = ptr->data;
		ptr->data = min;
	}
}

void inversion(pNode pHead) {
	int len = getLength(pHead);
	pNode a;
	pNode ptr;
	int temp;

	for (int i = 0; i < len / 2; i++) {
		ptr = pHead->pNext;
		for (int m = 0; m < i; m++)
			ptr = ptr->pNext;
		a = ptr;
		for (int k = i; k < len - i - 1; k++)
			ptr = ptr->pNext;
		temp = ptr->data;
		ptr->data = a->data;
		a->data = temp;
	}
}

2020.2.23 更新

了解到了一种非常棒的,健壮性很强的插入以及删除链表内容的算法

bool insert(pNode pHead, int pos, int value){
    int i = 0;
    pNode p = pHead;

    while (NULL != p && i < pos - 1){
        p = p->pNext;
        i++;
    }

    if (i>pos-1 || p == NULL)
        return False;

    //插入算法
}

这个判断方法可以处理所有关于pos的问题:1. 小于1;2. 大于 length + 1