剑指offer-第三章高质量代码(反转链表)
2024-09-27 10:12:52
题目:定义一个函数,输入一个链表的头节点,反转该链表并输出反转链表的头节点。
思路:对一个链表反转需要三个指针操作来保证链表在反转的过程中保证不断链,给链表一个行动指针pNode,对pNode指向的节点进行反转就是让它指向的下一个节点,变成指向上一个节点,因此我们要用一个指针pre来指向上一个节点。用pNext来保存pNode->m_pNext.避免在进行反转操作时,断链(如下图所示,对i进行反转)。
C++代码:
#include<iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
ListNode* createList(int a[],int k)
{
ListNode* pHead=NULL,*pNode=NULL;
for(int i=;i<k;i++)
{
ListNode* pNew=new ListNode();
pNew->m_nValue=a[i];
pNew->m_pNext=NULL;
if(pHead==NULL)
{
pHead=pNew;
pNode=pNew;
}
else
{
pNode->m_pNext=pNew;
pNode=pNode->m_pNext;
}
}
return pHead;
}
void printList(ListNode* pHead)
{
ListNode* p=pHead;
while(p!=NULL)
{
cout<<p->m_nValue<<" ";
p=p->m_pNext;
}
cout<<endl;
}
//递归实现
//注意判断oldList!=NULL的情况
ListNode *reverse(ListNode *oldList,ListNode *newHead=NULL)
{
if(oldList!=NULL)
{
ListNode *next=oldList->m_pNext;//记录上次反转后的链表
oldList->m_pNext=newHead;//将当前节点插入到翻转后链表的开头
newHead=oldList;//递归处理剩余的链表
return (next==NULL)?newHead:reverse(next,newHead);
}
return NULL;
}
ListNode *ReverseList(ListNode * pHead)
{
ListNode *pReversedHead=NULL;
ListNode *pNode=pHead;
ListNode *pPrev=NULL;
if(pHead==NULL)
return NULL;
while(pNode!=NULL)
{
ListNode *pNext=pNode->m_pNext; if(pNext==NULL)
pReversedHead=pNode;
pNode->m_pNext=pPrev; pPrev=pNode;
pNode=pNext;
}
return pReversedHead;
}
void main()
{
int a[]={,,,,};
ListNode* pHead=createList(a,);
printList(pHead);
ListNode* pReversedHead=ReverseList(pHead);
printList(pReversedHead);
}
Java代码:
public class ReverseLink { public static class ListNode
{
public int m_nValue;
public ListNode m_pNext;
}
//创建链表
public static ListNode CreateLink(int a[],int k)
{
ListNode Head=null,q=null;
for(int i=;i<k;i++)
{
ListNode pNew=new ListNode();
pNew.m_nValue=a[i];
pNew.m_pNext=null;
if(Head==null)
{
Head=pNew;
q=pNew;
}
else
{
q.m_pNext=pNew;
q=q.m_pNext;
} }
return Head;
}
//从头到尾打印列表
public static void printLink(ListNode pHead)
{
ListNode p=pHead;
while(p != null)
{
System.out.print(p.m_nValue+" ");
p=p.m_pNext;
}
System.out.println("\n");
}
//反转链表
public static ListNode reverseList(ListNode pHead)
{
ListNode pReversedHead=null;
ListNode pNode=pHead;
ListNode pre=null;
if(pHead==null)
return null; while(pNode!=null)
{
ListNode pNext=pNode.m_pNext;
if(pNode.m_pNext==null)
pReversedHead=pNode;
pNode.m_pNext=pre;
pre=pNode;
pNode=pNext;
}
return pReversedHead;
}
public static void main(String[] args) {
int a[]={,,};
ListNode Head=CreateLink(a,);
printLink(Head);
ListNode pReversedHead=reverseList(Head);
printLink(pReversedHead);
} }
最新文章
- js算数优先级
- Java中的private protected public和default的区别
- eclipse maven update error 解决方法
- jQuery 浮动标签插件,帮助你提升表单用户体验
- logrotate关于日志轮询和分割
- 数据爬取ing
- python+selenium实现跨浏览器兼容性测试
- 编程精粹:编写高质量的C语言代码———笔记一
- SQL技术内幕二DDL
- centos 安装node js环境
- 延迟N秒执行某个方法
- JavaScript 的数组操作--删除元素
- Swing入门
- 关于定时发送服务的解决办法(PHP)
- js脚本根据身份证号获取性别、年龄、家庭地址、生日
- MongoDB服务无法启动,windows提示发生服务特定错误:100
- JS:指定FPS帧频,requestAnimationFrame播放动画
- mybatis中获取参数
- DevExpress v17.2新版亮点—WPF篇(七)
- Unix系统编程()执行非局部跳转:setjmp和longjmp