长春建设网站制作,学网站建设难,机械厂网站模板,罗湖网站制作公司原题链接#xff1a;https://leetcode.cn/problems/reverse-linked-list/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
方法一#xff1a;三指针翻转法
使用三个结构体指针n1#xff0c;n2#xff0c;n3#xff0c;原地修改结点…原题链接https://leetcode.cn/problems/reverse-linked-list/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
方法一三指针翻转法
使用三个结构体指针n1n2n3原地修改结点指向。
就是让n1先指向空指针NULLn2指向头结点n3指向头结点下一个结点。
用n2进行遍历。然后让n1指向n2n2指向n3n3指向n3的下一个结点。如此循环遍历直到n2指向空指针NULL时停止。
最后返回n1即可。 这里为什么要用三个指针呢
因为如果只用两个指针那么我们让n1指向n2后链表的连接就断了找不到原链表n2的下一个结点了。 同时我们需要注意一些临界条件和特殊情况。
比如链表是空的我们就让最后返回空即可。
一般情况至少有一个结点存在所以我们得在n2不为空的情况下(即if(n2))让n3指向n2的下一个结点。n3n2-next
遍历过程中n3要指向下一个结点那么n3就不能是空指针即if(n3) n3n3-next
方法二头插法
对每一个结点都进行头插 3. 代码实现
方法一
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode *n1,*n2,*n3;n1NULL;n2head;if(n2)n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
} 方法二
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode *curhead;struct ListNode *newheadNULL;while(cur){struct ListNode *nextcur-next;//头插cur-nextnewhead;newheadcur;curnext;}return newhead;
}
