[E链表] lc206. 反转链表(反转链表+模板题)

文章目录

1. 题目来源2. 题目说明3. 题目解析方法一：迭代+原地逆置方法二：递归方法三：纯秀操作

1. 题目来源

链接：lc206. 反转链表

2. 题目说明

3. 题目解析

方法一：迭代+原地逆置

很经典，很易错，不要忘记处理最后的 head->next = NULL 情况。

参见代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if (!head) return head; auto a = head, b = a->next; while (b) { auto c = b->next; b->next = a; a = b; b = c; } head->next = NULL; return a; } };

方法二：递归

官方题解很清楚，LaTeX 公式在这敲太慢了。 这位题解下评论也是很清楚的阐述了整个递归过程。

参见代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if (!head || !head->next) return head; ListNode *p = reverseList(head->next); head->next->next = head; head->next = NULL; return p; } };

方法三：纯秀操作

貌似直接交换内存啥的，看了半天没看懂 😦，打开了 VS 单步调试+查看内存才搞清楚。是相当于逆置了 next 指针。

建议看了 5 min 还没啥思绪的就去写个代码调试下，很有帮助，这个也是如评论区大佬所讲：代码基础。

这是我写的一个小 demo 可供参考，是按顺序转移的，仔细观察下 next 指针的变化情况。

参考代码如下：

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *p = NULL; for(p; head; swap(head,p)) swap(p,head->next); return p; } };