【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;
} 
//一般来说如果要改变链表指针结点的值一般利用传递指针的指针 


相关文章
|
9月前
|
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
58 0
链表带头和不带头的区别及其应用
链表带头和不带头的区别及其应用
158 0
|
10月前
链表反转问题
链表反转问题
59 0
|
10月前
|
【算法】链表反转
【算法】链表反转
63 0
Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题
Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题
120 0
使用Java实现单向链表,并完成链表反转。
算法和数据结构是程序员逃不过的一个坎,所以趁着闲余时间,开始学习基础的算法和数据结构。这里记录下自己实现简单的单项链表的过程,如有错误,敬请指正。
链表——206. 反转链表(这题很重要)
本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助
链表——206. 反转链表(这题很重要)