怎么做一个网站平台,网站必备功能,公司网站建设需要些什么要求,网络服务商是指操作系统#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言#xff1a;C11
题目描述
输入一个链表#xff0c;输出该链表反转之后的链表。例如#xff1a;
输入: 1-2-3-4-5-NULL
输出: 5-4-3-2-1-NULL
解决方案
这个… 操作系统ubuntu22.04 IDE:Visual Studio Code 编程语言C11
题目描述
输入一个链表输出该链表反转之后的链表。例如
输入: 1-2-3-4-5-NULL
输出: 5-4-3-2-1-NULL
解决方案
这个问题可以通过多种方法解决包括递归法和迭代法。下面分别介绍这两种方法。
方法一迭代法
使用三个指针来逐步反转链表中的每一个节点直到遍历完整个链表。 代码实现C
struct ListNode {int val;ListNode* next;ListNode( int x ) : val( x ), next( nullptr ) {}
};ListNode* reverseList( ListNode* head )
{ListNode* prev nullptr; // 前驱节点ListNode* curr head; // 当前处理的节点while ( curr ! nullptr ){ListNode* nextTemp curr-next; // 暂存当前节点的下一个节点curr-next prev; // 将当前节点指向前驱节点prev curr; // 移动前驱节点到当前节点curr nextTemp; // 移动到下一个待处理节点}return prev; // 新的头节点是原链表的最后一个节点
}int main()
{ListNode* node1 new ListNode(1);node1-next new ListNode(2);node1-next-next new ListNode(3);node1-next-next-next new ListNode(4);node1-next-next-next-next new ListNode(5);ListNode* res reverseList(node1);ListNode *head res;while(res ! nullptr){std::cout res-valstd::endl;res res-next;}
}输出
5
4
3
2
1方法二递归法
递归地反转链表对于每个节点假设其后续节点已经被正确反转然后调整当前节点的指向。
代码实现C
struct ListNode {int val;ListNode* next;ListNode( int x ) : val( x ), next( nullptr ) {}
};
ListNode* reverseList( ListNode* head )
{// 基本情况如果头节点为空或只有一个节点则直接返回头节点if ( head nullptr || head-next nullptr ){return head;}// 递归调用反转剩余链表ListNode* p reverseList( head-next );// 反转当前节点与下一个节点之间的连接head-next-next head;head-next nullptr;return p; // 返回新的头节点
}int main()
{ListNode* node1 new ListNode(1);node1-next new ListNode(2);node1-next-next new ListNode(3);node1-next-next-next new ListNode(4);node1-next-next-next-next new ListNode(5);ListNode* res reverseList(node1);ListNode *head res;while(res ! nullptr){std::cout res-valstd::endl;res res-next;}
}输出
5
4
3
2
1
