首页 > 代码库 > 用两种递归思路与循环实现单链表的反转
用两种递归思路与循环实现单链表的反转
typedef struct ListNode{ int data; struct ListNode *next; }ListNode; //递归一 ListNode *ReverseList (ListNode *pHead, ListNode *nHead = NULL) { //每次取下第一个节点头插法创建新链表 //nHead为反转后链表的头节点 if(pHead == NULL) return NULL; ListNode *pNext = pHead -> next; pHead -> next = nHead; nHead = pHead; if (pNext == NULL) return nHead; else return ReverseList (pNext, nHead); } //递归二 ListNode *ReverseList (ListNode *pHead) { //递归到链表的最后一个将其指针反转 if (pHead == NULL || pHead -> next == NULL) return pHead; else { ListNode *nHead = ReverseList (pHead -> next); //将最后两个节点反转 pHead ->next ->next = pHead; pHead ->next = NULL; return nHead; //这是反转后链表的头节点 } } //循环 ListNode *ReverseList (ListNode *pHead) { //每次取下第一个节点头插法构造新链表 ListNode *nHead = NULL; ListNode *pNode = pHead; //当前取下的节点 ListNode *prev = NULL; while (pNode != NULL) { ListNode *pNext = pNode -> next; if (pNext == NULL) nHead = pNode; //到达链表的最后一个节点 pNode -> next = prev; prev = pNode; pNode = pNext; } return nHead; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。