【27】链表反转

简介: 题目:给定一个单链表的头结点要求反转该链表并要求不能改变更改链表的结构分析:1. 假设一个链表如下    headNode -> node1 -> node2 -> node3 -> node4 -> NULL2.


题目:给定一个单链表的头结点要求反转该链表并要求不能改变更改链表的结构


分析:

1. 假设一个链表如下

    headNode -> node1 -> node2 -> node3 -> node4 -> NULL

2. 则反转完这个链表之后,希望得到如下链表

    NULL <- headNode <- node1 <- node2 <- node3 <- node4

3. 此时链表的头结点变成了node4,我们可以枚举整个链表,对每一个结点我们保存下前面一个结点和下面一个结点,然后更改结点内部指向下一结点的指针属性

    例如node1的前面一个结点preNode为headNode,下面一个结点nextNode为node2,把node1->nextNode = headNode,然后更新preNode = node1,即可。


4. 实例代码

//链表结点
struct ListNode{
    int value;
	ListNode *nextNode;	   
}; 

//反转链表,参数是指针的指针这样才是地址传递 
ListNode* RevertList(ListNode **headNode){
	 //如果空链表直接返回 
	 if((*headNode) == NULL){
	     return NULL;
     }
     ListNode *preNode = NULL;
     ListNode *curNode = (*headNode);
	 while(curNode != NULL){
         ListNode *nextNode = curNode->nextNode;
         curNode->nextNode = preNode;
         preNode = curNode;
         curNode = nextNode;
	 }
	 return preNode;
} 
//一般来说如果要改变链表指针结点的值一般利用传递指针的指针 


相关文章
反转链表II
链表这部分的题,不少都离不开单链表的反转,参考:反转一个单链表 这道题加上哨兵位的话会简单很多,如果不加的话,还需要分情况一下,像是从头节点开始反转还是头节点以后开始反转,有了哨兵位后就只有一种情况了。 malloc一个哨兵位,next指向head,遍历两次,一次找起点,,开始节点的前一个节点保存下来,为了连接reverse返回的节点地址;一次找结束,结束的节点next节点保存下来,并使该节点的next指针置空,剩下的就是连接的问题,比较简单。
58 0
|
10月前
链表反转问题
链表反转问题
59 0
|
10月前
|
【算法】链表反转
【算法】链表反转
63 0
|
10月前
每日一题——回文链表
每日一题——回文链表
【剑指offer】-反转链表-15/67
【剑指offer】-反转链表-15/67
剑指offer 23. 反转链表
剑指offer 23. 反转链表
83 0
洛谷(2947)向右看齐-单调栈-链表
单调栈对新手来说不好理解,但链表就特别简单,但在有时间限制的竞赛中,很容易超时,因此如果实在要使用链表,注意使用链表的类型,Java提供的两种实现链表的方式
反转链表(剑指offer 24)
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等