前言

本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记，如有侵权，立即删除。

一、题目

1、原题链接

206.反转链表

2、题目描述

二、解题报告

1、思路分析

大致思路：不需要重新定义新链表，只要修改链表中所有指针的指向即可。

1. 法1：双指针

• 定义两个指针pre和cur从链表头部开始指向两个相邻节点来遍历整个链表，从而改变指针的指向（pre初始为空、cur初始为头节点）；
• 需要注意：在改变指针指向前需要先临时存储下一个需要改变指针指向的节点，否则在改变指针后操作的话，会导致节点丢失（无法找到下一个节点）。

2. 法2：递归

• 确定递归出口：cur为空时，递归结束；
• 确定递归体：reverse(pre, cur)函数改变pre、cur指向节点的指针；
• 递归方法实质是对双指针方法的代码简化与改写，思路一致。

2、代码详解

1. 法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) {} * }; */classSolution{public:ListNode*reverseList(ListNode*head){ListNode*pre=nullptr;ListNode*cur=head;while(cur!=NULL){// cur为NULL时说明链表已遍历完（循环体只访问cur->next，所以保证cur非空即可，不需要cur->next也非空）ListNode*tmp=cur->next;// tmp保存下一个要改变指针指向的节点cur->next=pre;// 注意下述两个操作不能颠倒pre=cur;cur=tmp;}// 反转后pre即头节点returnpre;}};

2. 法2：递归

/** * 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) {} * }; */classSolution{public:ListNode*reverse(ListNode*pre,ListNode*cur){//递归出口if(cur==nullptr){returnpre;}ListNode*tmp=cur->next;cur->next=pre;//等同于双指针写法的pre = cur;cur = tmp;returnreverse(cur,tmp);}ListNode*reverseList(ListNode*head){returnreverse(nullptr,head);// 等同于双指针写法中的初始化操作}};

三、知识风暴

• 双指针；
• 递归
  • 确定递归出口；
  • 确定递归体。