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

leetcode_206 反转链表

article 2025/8/20 21:54:32

1. 题意

原地反转链表，非常经典的一道题。

2. 解决

2.1 非递归

非递归的比较好理解；链表需要维护前驱和后继两个信息，当我们要更改后继时，先要把原来的后继先存起来。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {// A->B->C// next = getNext;// cur->next = pre// pre = cur;// cur =  next;// //          pre//          |//          V//  null <- A    B->C // null <- A     ListNode *pre = nullptr;ListNode *cur = head;while ( cur ) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}};

2.2 递归

递归的比较难理解一些。

由于返回的是翻转后的头节点，因此需要不断的递归到没有后继节点的最后一个节点, 它就是反转后链表的头节点了。

而返回的链表的最后一个节点是head->next ，将它的指向改成当前节点。同时我们还需要将当前节点的next域置空，否则无法将原先的头指空。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {// A->B->Cif ( head == nullptr || head->next == nullptr) {return head;}ListNode *newHead = reverseList( head->next );ListNode *newListTail = head->next;newListTail->next = head;head->next = nullptr;return newHead;}};