[数据结构与算法][LeetCode] 206.反转链表

LeetCode 206.反转链表

思路

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); 
    }
};