夯实C++基础之刷题：链表——2链表反转

题目

题解

1、双指针 每一次都局部翻转

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

2、递归（递归总是想不明白 ，我简想成只有两个元素，那么就是让当前节点的下一个节点的next指针指向当前节点，当前节点的next指针指向null，从而实现局部反转，递归下，递归都出栈时完成反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);//递归
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};