一. 力扣LCR 024. 反转链表

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

递归

递归终止条件：当链表为空或只有一个节点时，递归终止，直接返回头节点

递归调用：在每次递归调用中，我们传入当前节点的下一个节点作为新的头节点。这样，递归调用会逐步深入刀链表的尾部

反转操作：当递归调用返回时，我们得到了剩余部分(除了头节点)的反转链表， 此时：

将当前节点的下一个节点的next指针指向前一个节点。

将当前节点的next指针设为NULL，断开与原始链表的连接，完成当前节点的反转

返回新的头节点

每次递归调用返回的都是新的头节点，在递归过程中，这个新的头节点会逐步向链表的头部移动

接下来我们来更为直观的举例来解释

假设我们有以下链表：1->2->3->-4->5

• 第一次递归调用：传入1，递归到2。
• 第二次递归调用：传入2，递归到3。
• 第三次递归调用：传入3，递归到4。
• 第四次递归调用：传入4，递归到5。
• 递归终止，5没有下一个节点，返回5作为新的头节点
• 返回上一层：在4的递归调用中，将4的next指针指向前一个节点，并将4的next设为NULL，然后返回5作为新的头节点
• 以此类推，每次返回都会进行类似的反转操作，知道返回最初的调用

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

二. 力扣 2. 两数相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

三.力扣 24. 两两交换链表中的节点

ListNode* swapPairs(ListNode* head) {
			ListNode* dummyHead = new ListNode(0);//设置一个虚拟头节点
dummyHead->next = head;//将虚拟头结点指向head，这样方便后面做删除操作
ListNode* cur = dummyHead;
while (cur->next != nullptr && cur->next->next != nullptr)
{
	ListNode* tmp = cur->next;
	ListNode* tmp1 = cur->next->next->next;

	cur->next = cur->next->next;
	cur->next->next = tmp;
	cur->next->next->next = tmp1;

	cur = cur->next->next;
}