链表

什么是链表？

百度百科显示如下：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

简化理解下：
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表分为：单链表、双链表、单向循环链表、双向循环链表
本文是对单向链表学习的一些基本操作

链表结构体的创建


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

链表的初始化


int main(int argc, char *argv[])
{
    ListNode *head = new ListNode(0);
    return (0);
}

链表的元素添加——(在结尾添加)


void add_list(ListNode* head, int val)
{
    ListNode* pNew = new ListNode(val);
    if(head == nullptr)
        head = pNew;
    else
    {
        ListNode* node = head;
        while(node->next != nullptr)
            node = node->next;
        node->next = pNew;
    }
    //head->val++;
}

链表的打印输出

循环遍历输出


void printf_list(ListNode *head)
{
    struct ListNode *temp;
    temp = head;
    while (1)
    if(temp != nullptr){
        cout << temp->val;
        temp = temp->next;      
    }else break;
    cout << "" << endl;
}

链表的创建

创建含有n个节点的链表


ListNode* creat_list(int n) 
{
	ListNode* head = new ListNode(0);
	ListNode* node;
	ListNode* end;
	end = head;
	for (int i = 1; i <= n; i++) 
    {
		node = new ListNode(i);//存放数据
		end->next = node;
		end = node;
		//靠end的移动来创建链表
	}
    head->val = n;//头节点不存放数据，记录节点个数
	return head;//头指针表示一个链表
}

链表的销毁

销毁head链表(留下表头）


ListNode* destroy_list(ListNode* head) 
{
	ListNode* node = head->next;
	ListNode* p = 0;
	while (node) {
		p = node;
		node = node->next;
		delete p;
	}
	head->val = 0;
}

链表查找数值

查找head链表中有无值k,注意要初始化结构体指针为0


ListNode* find_list(ListNode* head, int k)
{
	ListNode* temp = head->next;
	ListNode* p=0;
	while (temp && k != temp->val) {
		p = temp;//保留原节点
		temp = temp->next;
	}
	if (temp == 0)
		return 0;
	return temp;
}

链表查找节点

返回倒数k个节点


ListNode* find_Kcountdown(ListNode* head, int k)
{
	ListNode* fast = head;
	ListNode* slow = head;
	//快指针先行k步 fast-template
	for(int i = 0; i < k; i++){
		if(fast != NULL)
			fast = fast->next;
		//达不到k步说明链表过短，没有倒数k
		else
			return slow = NULL;
	}
	//快慢指针同步，快指针先到底，慢指针指向倒数第k个
	while(fast != NULL){
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

链表的节点插入

在第k个节点后插入data,支持尾插（不传k的值）和头插（k=0）


ListNode* insert_list(ListNode* head, int data, int k) 
{
	ListNode* node = head->next;
	ListNode* p = head;
	int  count = 0;
	while(node&&count++!=k){
		p = node;
		node = node->next;
	}
	ListNode* temp = new ListNode(data);
	temp->val = data;
	p->next = temp;
	temp->next = node;
	head->val++;
	return head;
}

链表的节点删除

删除第k个节点
删除倒数第k个节点

//删除第k个节点
ListNode* delete_node(ListNode* head, int k)
{
	ListNode* node = head->next;
	ListNode* p=0;
	for (int i = 1; i < k; i++) {
		p = node;
		node = node->next;
	}
	p->next = node->next;
	delete node;
	head->val--;
	return head;
}

// 删除倒数第k个节点
ListNode* delete_Nend(ListNode* head, int k)
{ 
	//添加表头 fast-template
	ListNode* res = new ListNode(-1);
	res->next = head;
	//当前节点
	ListNode* cur = head;
	//前序节点
	ListNode* pre = res;
	ListNode* fast = head;
	//快指针先行n步
	while(k--)
		fast = fast->next;
	//快慢指针同步，快指针到达末尾，慢指针就到了倒数第n个位置
	while(fast != NULL){
		fast = fast->next;
		pre = cur;
		cur = cur->next;
	}
	//删除该位置的节点
	pre->next = cur->next;
	//返回去掉头
	return res->next;
}

C++学习笔记——链表（一）