206. 反转链表

206. 反转链表

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

ListNode* reverseList(ListNode* head){
	ListNode* temp;   //保存cur的下一个结点   
	ListNode* cur=head;
	ListNode* pre =NULL;
	while(cur){
		tmp=cur->next;  //保存cur的下一个结点，因为接下来要改变cur->next
		cur->next=pre;  //反转 
		pre=cur;		//更新pre
		cur=temp;		//再更新cur
	}
	return pre;
}

/**
 * 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) {
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* tmp;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

递归

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};