LeetCode刷题(1)【链表】【反转链表】(C语言)
LeetCode刷题(1)【链表】【反转链表】(C语言)
半生瓜的blog
发布于 2023-05-12 21:17:17
发布于 2023-05-12 21:17:17
题目链接——206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
反转链表
思路一:反转指针。
在这里插入图片描述
在这里插入图片描述
本质上就是调转指针的方向。 首先我们定义两个指针,一个叫n1，一个叫n2。(Node1,Node2) 让n2指向第一个结点，让n1指向空。
在这里插入图片描述
n2->next指向n1。
在这里插入图片描述
但是，两个指针是反不转的。因为： 这里让n2->next指向n1，就是把n1的值存到n2的next上，n2->next原来存的是2的地址，现在存的是NULL，但是继续往后走的时候，我们发现找不到2了 。 所以要反转指针，两个指针是反不动的，要用3个。 前两个指针 反转，最后一个指针负责记录下一个位置。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
什么时候结束 n2 == NULL；
重复的条件用循环解决
- 初始条件
- 迭代过程
- 结束条件 画图看起来很浪费时间，但提升了写代码的体验，更好的解决问题。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL)
{
return NULL;
}
//初始化条件
struct ListNode* n1 = NULL,*n2 = head,*n3 = n2->next;
//结束条件
while(n2 != NULL)
{
//迭代过程
n2->next = n1;
//往后推移
//两个相等就是往后推移
n1 = n2;
n2 = n3;
if(n3 != NULL)
{
n3 = n3->next;
}
}
return n1;
} 思路二：头插法 取结点头插到新链表中。cur是当前操作结点，用一个next来保存下一个结点(同上)。 文字简单描述： 从原链表去一个点下来，放到新的链表中，当做新链表的头结点cur = newhead, 迭代往后走，取下一个结点… 代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* newHead = NULL;
while(cur != NULL)
{
struct ListNode* next = cur->next;
//头插法
cur->next =newHead;
newHead = cur;
cur = next;
}
return newHead;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读