//"slist.h"
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x) 
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);

	if (*pplist == NULL) {
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next!=NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		
	}

}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;

}


// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);

	//一个节点
	if ((*pplist)->next == NULL) {
		free(*pplist);
		*pplist = NULL;
	}

	//多个节点
	SListNode* tail = *pplist;
	while (tail->next->next!=NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;

}
void SListPopFront(SListNode** pplist) {
	// 防御性检查：拦截非法输入
	if (pplist == NULL) {
		fprintf(stderr, "Error: Invalid pointer in SListPopFront\n");
		return;
	}

	// 业务逻辑检查：空链表直接返回
	if (*pplist == NULL) {
		return;
	}

	SListNode* tmp = *pplist;
	*pplist = tmp->next;
	free(tmp);
}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？  

// 因为没有前置指针
// 若要在 pos 之前插入，必须从头节点开始遍历链表找到 pos 的前驱节点，时间复杂度为 O(n)
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	if (pos == NULL) return;
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？ 

//删除 pos 节点需要知道其前驱节点，而单链表无法直接获取前驱节点
// 必须从头遍历链表，时间复杂度为O(n)，删除 pos 之后的节点只需修改 pos->next，时间复杂度为O(1)。

void SListEraseAfter(SListNode* pos)
{
	if (pos == NULL || pos->next == NULL) return;
	SListNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
}

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (*pphead == pos) SListPushFront(pphead,x);
	else
	{
		SListNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		SListNode* newnode=BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}
}

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		// 头删
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur) {
		SListNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	*pphead = NULL;
}