/*********************************************************
题目:定义一个函数输入一个链表的头结点,反转该链表并输出反转
后链表的头结点。
**********************************************************/
#include<iostream>
#include<stdio.h>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode* pNext;
};
ListNode* createListNode(int value)
{
ListNode* pNewNode = new ListNode();
pNewNode->m_nValue = value;
pNewNode->pNext = NULL;
return pNewNode;
}
void connectListNode(ListNode* pNode1, ListNode* pNode2)
{
if(pNode1 == NULL || pNode2 == NULL)
return;
pNode1->pNext = pNode2;
}
//反转链表
ListNode* reverseList(ListNode* pHead)
{
if(pHead == NULL) //无效输入
throw exception("Invalid input!");
ListNode* pNode = pHead; //当前节点
ListNode* pPrev = NULL; //pNode前一节点
ListNode* pReversedNode = NULL; //反转后起始节点
while(pNode != NULL)
{
ListNode* pNext = pNode->pNext;
if(pNext == NULL)
pReversedNode = pNode;
pNode->pNext = pPrev;;
pPrev = pNode;
pNode = pNext;
}
return pReversedNode;
}
//打印链表
void printList(ListNode* pHead)
{
if(pHead == NULL)
printf("NULL");
while(pHead != NULL)
{
printf("%d\t",pHead->m_nValue);
pHead = pHead->pNext;
}
printf("\n");
}
//单元测试
//空节点
void test1()
{
reverseList(NULL);
}
//一个节点
void test2()
{
ListNode* pHead = createListNode(5);
ListNode* pNewHead = reverseList(pHead);
printList(pNewHead);
}
//一般情况
void test3()
{
ListNode* pNode1 = createListNode(1);
ListNode* pNode2 = createListNode(2);
ListNode* pNode3 = createListNode(3);
ListNode* pNode4 = createListNode(4);
connectListNode(pNode1,pNode2);
connectListNode(pNode2,pNode3);
connectListNode(pNode3,pNode4);
ListNode* pNewHead = reverseList(pNode1);
printList(pNewHead);
}
int main()
{
try
{
test2();
test3();
test1();
}
catch(exception ex)
{
cout<<ex.what();
}
return 0;
}
分享到:
相关推荐
描述了反转链表的用法,提供了两种方法,十分简单,实用。
反转链表 迭代法## 逐个节点反转## 更新指针位置## 返回反转后的头结点反转 a 到 b 之间的结点反转区间 [a, b) 的元素,注意是左闭右开K 个一组
LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...
反转链表C实现
反转链表.md
python 实现 反转链表
反转链表,记录了详细的题目解析思路以及Java语言的参考代码。 适合人群:学习算法和数据结构的程序员或学生,尤其是想系统学习链表操作的人。 能学到什么:掌握链表虚拟头节点设置方法;练习链表基本操作函数如增删...
使用Java语言实现剑指offer上面的第22题,反转链表。
22.反转链表1
c语言基础 c语言基础_c语言编程基础之链表操作示例_反转链表
反转链表 II.md
1.1 从尾到头打印链表内容——辅助栈 1.2 从尾到头打印链表内容——递归法 2.1 反转链表——普通循环反转 2.2 反转链表——头插法反转
015-反转链表题目描述输入一个链表,反转链表后,输出新链表的表头。思路从原链表的头部一个一个取节点并插入到新链表的头部。指针tmp指向还没进行反转的原链表头部
java基础面试题反转链表本资源系百度网盘分享地址
k个一组反转链表.md
递归反转链表的一部分.md
数组和链表(使用场景和反转链表) 数组和链表.pdf