/*********************************************************
题目:定义一个函数输入一个链表的头结点,反转该链表并输出反转
后链表的头结点。
**********************************************************/
#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;
}
分享到:
相关推荐
反转链表是链表操作中的经典问题,它要求改变链表中节点的指向,使得原来的前后顺序反转。本文将详细介绍如何使用一般方法和递归方法来反转单向链表。 ### 一般方法(迭代法) **步骤**: 1. 定义三个指针`pre`、`...
反转链表 迭代法## 逐个节点反转## 更新指针位置## 返回反转后的头结点反转 a 到 b 之间的结点反转区间 [a, b) 的元素,注意是左闭右开K 个一组
反转链表是一个常见的数据结构问题,它涉及到对链表节点的重新排列,使得原链表的后继节点变成前驱节点。在这个问题中,我们使用Java语言来解决剑指Offer系列书籍中的第22题——反转链表。下面将详细探讨这个问题的...
本资料包主要关注C语言编程中的链表操作,特别是反转链表这一核心技能。 首先,链表由一系列节点组成,每个节点包含两部分:数据域和指针域。数据域用于存储实际的数据,而指针域则指向下一个节点。链表可以是单向...
LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...
### 反转链表C实现 #### 知识点概览 本文将详细介绍如何使用C语言来实现链表的反转操作。链表是一种常见的线性数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。反转链表意味着重新组织这些...
以下是一个简单的迭代反转链表的C++实现,利用了STL中的`list`容器: ```cpp #include #include void reverseList(std::list<int>& lst) { std::list<int>::iterator prev = lst.end(); std::list<int>::...
在本文件中,我们看到了一个主题为“04-反转链表”的内容,下面我将详细解析这个文件中的知识点。 首先,文件中提到了数据结构和算法在大厂前端面试中的重要性。数据结构是指一组数据的组织、管理和存储格式,它...
在本压缩包中,我们关注的是Java编程语言在解决LeetCode第206题——反转链表的问题。LeetCode是一个在线平台,它提供了一系列的编程挑战,帮助开发者提高算法技能和解决问题的能力。在这个问题中,目标是反转一个...
反转链表是链表操作中常见的问题,它的核心在于改变节点之间的链接关系,使得原来的后继节点变为前驱节点。在本案例中,我们讨论的是单向链表的反转,即将一个正向排列的链表如1->2->3,转换为反向排列的链表3->2->1...
在每次递归调用中,我们先反转链表的剩余部分(即`head->next`),然后将`head`与新反转后的链表的头节点连接,最后断开`head->next`的下一个节点,防止形成环。递归的终止条件是链表为空或只有一个元素,此时无需...
本篇将深入探讨第206题——反转链表,这是一道常见的链表操作题目,对于理解和掌握链表的特性及其操作至关重要。 链表是一种线性数据结构,与数组不同,链表的元素并不在内存中连续存储。每个元素称为节点,包含两...
本压缩包文件“python-leetcode面试题解之第92题反转链表II.zip”专注于Python语言,具体解决的是LeetCode中的第92题——反转链表II。这个题目是链表操作的经典实例,对于理解和掌握链表的特性和操作具有很高的价值...
反转链表.md
### 使用迭代和递归两种方法反转链表 在计算机科学中,链表是一种常见的数据结构,广泛应用于多种算法和数据处理场景中。反转链表是一个经典的面试题目,它不仅能够考察求职者的编程基础,还能检验其对递归的理解...
python 实现 反转链表
反转链表,记录了详细的题目解析思路以及Java语言的参考代码。 适合人群:学习算法和数据结构的程序员或学生,尤其是想系统学习链表操作的人。 能学到什么:掌握链表虚拟头节点设置方法;练习链表基本操作函数如增删...
92反转链表 II.zip
Java语言实现反转链表代码示例 Java是一种广泛应用于软件开发的编程语言,而链表是编程中的一种重要数据结构。反转链表是链表操作中的一种基本操作,它可以应用于各种实际场景中。下面我们将详细介绍Java语言实现...