链表手撕代码（链表的创建、头插法、尾插法、部分反转、全部反转、链表的排序、链表的销毁）

链表作为基础数据结构中的必考知识点，考察指针操作。为了方便后期更好地总结学习，现将链表问题简单总结如下：

链表的创建、头插法、尾插法、部分反转、全部反转、链表的排序、链表的销毁。直接上代码：

#include <stdlib.h> 
#include<iostream>
#include<ctime>
#include<queue>
#include<functional>
using namespace std;
/* Definition for singly - linked list.*/
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	
};

ListNode* reverseList(ListNode* head) {
	ListNode *prev = NULL;
	while (head) {
		ListNode* tmp = head->next;
		head->next = prev;
		prev = head;
		head = tmp;
	}
	return prev;
}
ListNode* insertNode(ListNode* head, int data) {
	ListNode* tmp = head;
	if (NULL == tmp)
		head = new ListNode(data);
	while (tmp->next) {
		tmp = tmp->next;
	}
	tmp->next = new ListNode(data);
	return head;
}
void printListNode(ListNode* head) {
	ListNode* tmp = head;
	while (tmp) {
		cout << tmp->val << " ";
		tmp = tmp->next;
	}
}
void freeListNode(ListNode* head) {
	ListNode* tmp = head;
	while (tmp) {
		ListNode* t = tmp->next;
		delete tmp;
		tmp = t;
	}
}

ListNode* reverseFromToListNode(int m, int n, ListNode* head) {
	if (m == n)return head;
	ListNode*pre = new ListNode(-1);

	pre->next = head;
	ListNode*prehead = pre;
	for (int i = 0; i < m; i++)
	{
		prehead = prehead->next;
	}

	n -= m;  // n >= 1
	ListNode* pstart = prehead->next;
	//链表反转涉及到四个节点
	for (int i = 1; i <= n; i++)
	{
		ListNode* p = pstart->next;
		pstart->next = p->next;
		p->next = prehead->next;
		prehead->next = p;
	}

	return pre->next;
}

ListNode* reverseAll(ListNode* head) {
	ListNode* pre = NULL;
	while (head) {
		ListNode* t = head->next;
		head->next = pre;
		pre = head;
		head = t;
	}
	return pre;
}
ListNode* sort(ListNode *head)
{
	ListNode *prev = NULL;
	ListNode *cur = NULL;
	ListNode *pre_new = NULL;
	ListNode *tmp = NULL;
	bool b_head = false;
	if (!head) {
		cout << "链表为空！" << endl;
		return head;
	}
	cur = head;
	while (cur) {
		if (!b_head)
		{
			prev = cur;
			cur = cur->next;
			prev->next = NULL;
			b_head = true;
		}
		else {
			if (cur->val<prev->val)  //数据小于首结点
			{
				pre_new = cur->next;
				cur->next = prev;
				prev = cur;
				cur = pre_new;
			}
			else { //加入到新链表
				pre_new = prev;
				while (pre_new->next)    //遍历新的链表
				{
					if ((cur->val)>(pre_new->next->val))
					{
						tmp = cur->next;
						cur->next = pre_new->next;
						pre_new->next = cur;
						cur = tmp;
					}
					else {
						pre_new = pre_new->next;
					}
				}
				//如果是结尾结点
				if (!(pre_new->next)) {
					tmp = cur->next;
					cur->next = NULL;
					pre_new->next = cur;
					cur = tmp;
				}
			}
		}
	}
	return prev;
}

ListNode* sortList(ListNode* head) {
	if (!head || !head->next) return head;
	//优先队列的第一个元素的是最大值
	priority_queue<int, std::vector<int>, std::greater<int>> q;
	ListNode* cur = head;
	while (cur) {
		q.push(cur->val);
		cur = cur->next;
	}
	cur = head;
	while (!q.empty()) {
		cur->val = q.top();
		q.pop();
		cur = cur->next;
	}
	return head;
}
ListNode* Sort(ListNode* SL)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/
{
	ListNode* p;
	ListNode* q;
	int temp;
	// 通过交换数据的方式
	for (p = SL; p != NULL; p = p->next)
	{
		for (q = p->next; q != NULL; q = q->next)
		{
			if (p->val > q->val)
			{
				temp = q->val;
				q->val = p->val;
				p->val = temp;
			}
		}
	}
	return SL;
}

int main() {
	srand(time(NULL));
	ListNode* head = new ListNode(0);
	for (int i = 0; i < 10; ++i) {
		head = insertNode(head, rand() % 100 + 100);   // 产生[0, 100)的随机数
	}
	printListNode(head);

	cout<< endl << "reverse the listnode between 2 and 4" << endl;
	head = reverseFromToListNode(2, 4, head);
	printListNode(head);

	cout << endl << "reverse all the ListNode" << endl;
	head = reverseAll(head);
	printListNode(head);

	cout << endl << "after ListNode* sort" << endl;
	//head = Sort(head);
	head = sortList(head);
	printListNode(head);
	freeListNode(head);
	return 0;
}

另外附上：链表的区间反转的示意图帮助理解消化。

链表排序问题：

一种是交换节点的数据，方法实现起来简单，但是效率低下。

第二种方法采用stl标准容器，即优先队列。