当前位置：首页 > news >正文

C++面试(9)-----反转链表

news 2025/6/14 8:28:01

操作系统：ubuntu22.04
IDE:Visual Studio Code
编程语言：C++11

题目描述

输入一个链表，输出该链表反转之后的链表。例如：

输入: 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->val<<std::endl;res = res->next;}
}

输出：

方法二：递归法

递归地反转链表，对于每个节点，假设其后续节点已经被正确反转，然后调整当前节点的指向。

代码实现（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->val<<std::endl;res = res->next;}
}