二：单链表的反转-递归和循环方式实现

本文主要是介绍二：单链表的反转-递归和循环方式实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 单链表的创建、打印和释放见博客 一：单链表的创建、打印和释放

1. 递归方式实现单链表的反转

/***@param pList NODE_t * ：带头结点的单链表的第一个有效结点*/
NODE_t * SListRecur(NODE_t *pFirst) {if (pFirst == NULL || pFirst->pNext == NULL) {return pFirst;}NODE_t *pNewNode = SListRecur(pFirst->pNext);pFirst->pNext->pNext = pFirst;pFirst->pNext = NULL;return pNewNode;
}/*** 通过递归方式实现单链表的反转* 原来的单链表成为反转后的单链表**/
NODE_t * ReverseSListRecur(NODE_t *pList) {if (pList == NULL || pList->pNext == NULL) {printf("single list is empty\n");return pList;}NODE_t *pHead = pList;NODE_t *pNewHead = SListRecur(pHead->pNext);pHead->pNext = pNewHead;return pHead;
}

2. 循环方式实现单链表的反转

​​/*** 通过循环方式实现单链表的反转* 原来的单链表成为反转后的单链表** @param pList NODE_t * ：单链表的头结点*/
NODE_t * ReverseSListCirle(NODE_t *pList) {if (pList == NULL || pList->pNext == NULL) {printf("single list is empty\n");return pList;}NODE_t *pHead = pList;NODE_t *pPre = pHead->pNext;NODE_t *pCur = pPre->pNext;NODE_t *pNext = NULL;/* 第一个有效结点的后继不设置为空，会造成无限循环 */pPre->pNext = NULL;/* 使用三个指针指示当前，前一个，后一个结点地址每次使当前、前一个结点反转，然后指针后移 */while (pCur != NULL) {pNext = pCur->pNext;pCur->pNext = pPre;pPre = pCur;pCur = pNext;}pHead->pNext = pPre;return pHead;
}

3. 测试代码

int main() {/* 创建单链表，递归遍历单链表 */int aArray[6] = { 1, 4, 5, 2, 1, 6 };NODE_t *pList1 = CreateArraySList(aArray, 6);ShowSList(pList1);NODE_t *pNew1 = ReverseSListRecur(pList1);ShowSList(pNew1);FreeSList(pList1);/* 创建单链表，循环遍历单链表 */NODE_t *pList2 = CreateArraySList(aArray, 6);ShowSList(pList2);NODE_t *pNew2 = ReverseSListCirle(pList2);ShowSList(pNew2);FreeSList(pList2);return 0;
}

 

这篇关于二：单链表的反转-递归和循环方式实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---