思路
1)再定义一个新链表(弊端:容易导致内存空间的浪费) 2)直接对原链表进行操作,改变每个结点的next指针指向的方向,从而实现链表的反转(推荐) 双指针法:定义一个指针cur指向原链表的头结点,再定义一个指针pre初始化为nullptr Step1:将cur->next结点用临时指针tmp保存一下 Step2:将cur->netx指向pre Step3:更新cur和pre指针,分别向后移动cur指针和pre指针 Step4:循环步骤1、2、3,循环结束条件:cur为空 递归法: 思路与双指针法类似,不断地将cur指向pre的过程,递归结束条件同样是cur为空, 只不过对cur、pre的初始化写法变了
代码实现
1)双指针法:
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *cur = head; ListNode *pre = nullptr; while(cur) { ListNode *tmp = cur->next; cur->next = pre; // 更新cur和pre指针 pre = cur; cur = tmp; } return pre; } };
2)递归法
class Solution { public: ListNode *reverse(ListNode *pre, ListNode *cur){ if(cur == nullptr) return pre; ListNode *tmp = cur->next; cur->next = pre; return reverse(cur, tmp); } ListNode* reverseList(ListNode* head) { return reverse(nullptr, head); } };