链表是一种动态数据结构。 常见的面试题：单向链表、从尾到头打印链表、删除链表的节点、链表中倒数第K个节点、反转链表、合并两个排序的链表、两个链表的第一个公共节点等
方法1：可以改变链表方向实现 方法2：采用栈的“后进先出”方案 方法3：递归函数（当链表非常长时，就会导致函数调用的层级很深，从而导致函数调用栈溢出 本文采用“方法2”
/* 链表结构体 */ typedef struct _ST_NODE_ { void *pDataAddr; /* 存放的数据 */ unsigned dataLen; /* 数据长度 */ struct _ST_NODE_ *pNextNode; /* 下一个节点的指针 */ } ST_NODE, *PST_NODE; /* 栈结构体 */ typedef struct _ST_STACK_ { ST_NODE *pHeadNode; /* 头结点 */ ST_NODE *pTailNode; /* 尾节点 */ int len; /* 栈的长度 */ int offset; /* 地址偏移量 */ int top; /* 栈顶的下标 */ void *pAddr; /* 存放栈的首地址 */ } ST_STACK, *PST_STACK; /************************************************* Function: st_initStack Description: 初始化栈内容 Parameter: pStStack 栈 size 单个变量需要的内存大小 len 栈的长度 Output: None Return: -1失败 0是成功 *************************************************/ int st_initStack(ST_STACK *pStStack, int size, int len) { if (!pStStack || size <= 0) { printf("param err size:%d\n", size); return -1; } pStStack->len = len; pStStack->offset = size; if (pStStack->len <= 0) { printf("param err pStStack->len:%d\n", pStStack->len); return -1; } pStStack->pAddr = malloc(size * pStStack->len); if (!pStStack->pAddr) { printf("not enough Malloc\n"); return -1; } pStStack->top = -1; return 0; } /************************************************* Function: st_fullStack Description: 判断栈是否已满 Parameter: pStStack 栈 Output: None Return: -1失败 0是成功 *************************************************/ bool st_fullStack(ST_STACK *pStStack) { if (!pStStack) { printf("param err size\n"); return -1; } return pStStack->top + 1 >= pStStack->len; } /************************************************* Function: st_emptyStack Description: 判断栈是否空闲 Parameter: pStStack 栈 Output: None Return: -1失败 0是成功 *************************************************/ bool st_emptyStack(ST_STACK *pStStack) { if (!pStStack) { printf("param err size\n"); return -1; } return pStStack->top == -1; } /************************************************* Function: st_topStack Description: 查找栈顶 Parameter: pStStack 栈 Output: None Return: -1失败 0是成功 *************************************************/ int st_topStack(ST_STACK *pStStack, void **pDst) { if (!pStStack) { printf("param err size\n"); return -1; } if (st_emptyStack(pStStack)) { printf("1stack empty!!!\n"); return -1; } *pDst = pStStack->pAddr + pStStack->top * pStStack->offset; printf("param %p, %d,%d, %p\n", pStStack->pAddr, pStStack->top, pStStack->offset, *pDst); return 0; } /************************************************* Function: st_pushStack Description: 变量入栈 Parameter: pStStack 栈 pStValue 单个栈的内容 size 单个变量需要的内存大小 Output: None Return: -1失败 0是成功 *************************************************/ int st_pushStack(ST_STACK *pStStack, void *pStValue, int size) { if (!pStStack || !pStValue || size <= 0) { printf("param err size:%d\n", size); return -1; } if (pStStack->len <= 0) { printf("param err pStStack->len:%d\n", pStStack->len); return -1; } if (st_fullStack(pStStack)) { printf("stack full!!!\n"); return -1; } pStStack->top++; memcpy(pStStack->pAddr + pStStack->top * pStStack->offset, pStValue, size); return 0; } /************************************************* Function: st_popStack Description: 变量出栈 Parameter: pStStack 栈 Output: None Return: -1失败 0是成功 *************************************************/ int st_popStack(ST_STACK *pStStack) { if (!pStStack) { printf("param err\n"); return -1; } if (st_emptyStack(pStStack)) { printf("stack empty!!!\n"); return -1; } pStStack->top--; return 0; } /************************************************* Function: st_putNodeToStack Description: 节点放到栈里 Parameter: pNode 节点 pStStack 堆栈 Output: None Return: -1失败 0是成功 *************************************************/ void st_putNodeToStack(ST_NODE *pNode, ST_STACK *pStStack) { int ret = 0; if (!pStStack || !pNode) { return; } while (pNode != NULL) { ret = st_pushStack(pStStack, pNode->pDataAddr, pNode->dataLen); if (ret != 0) { printf("st_pushStack err \n"); return; } pNode = pNode->pNextNode; } return; } /************************************************* Function: st_pthread_getPriorityScope Description: 获取线程最大和最小优先级 Parameter: pMaxPriority 最大优先级 pMinPriority 最小优先级 Output: None Return: -1失败 0是成功 *************************************************/ void st_getPrintStack(ST_STACK *pStStack, void **pDst) { if (!pStStack) { return; } printf("pStStack->top:%d\n", pStStack->top); if (!st_emptyStack(pStStack)) { st_topStack(pStStack, pDst); printf("pStStack->pst:%p\n", *pDst); st_popStack(pStStack); } return; } int main(int argc, char *argv[]) { ST_NODE *pHead = (ST_NODE *)malloc(sizeof(ST_NODE)); /* pEnd 目的是采用尾插法而不是头插法 */ ST_NODE *pEnd = NULL; pHead->pNextNode = NULL; int i = 0; int lenNode = 7; ST_STACK stStack; void *pDst = NULL; ST_TEST_NODE_INFO *pTestNodeDst = NULL; pEnd = pHead; memset(&stStack, 0, sizeof(stStack)); for (i = 0; i < lenNode; i++) { ST_TEST_NODE_INFO *pTestNodeInfo = NULL; pTestNodeInfo = (ST_TEST_NODE_INFO *)malloc(sizeof(ST_TEST_NODE_INFO)); pTestNodeInfo->val = i + 1; ST_NODE *pS = (ST_NODE *)malloc(sizeof(ST_NODE)); pS->dataLen = sizeof(ST_TEST_NODE_INFO); pS->pDataAddr = pTestNodeInfo; pEnd->pNextNode = pS; pEnd = pS; } pEnd->pNextNode = NULL; /* 初始化栈 */ st_initStack(&stStack, sizeof(ST_NODE), 20); printf("len:%d, offset:%d\n", stStack.len, stStack.offset); /* 将节点放到栈空间 */ st_putNodeToStack(pHead->pNextNode, &stStack); printf("len:%d, offset:%d, top:%d\n", stStack.len, stStack.offset, stStack.top); while (!st_emptyStack(&stStack)) { st_getPrintStack(&stStack, &pDst); printf("pDst:%p\n", pDst); if (pDst) { pTestNodeDst = (ST_TEST_NODE_INFO *)pDst; printf("val:%d\n", pTestNodeDst->val); } } }