题目描述

反转一个单链表。

解题思路

使用迭代或递归的方式来反转链表。

解题步骤

迭代方法：

1. 初始化三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点）。
2. 遍历链表，每次将当前节点的 next 指向前一个节点，然后更新 prev、curr、next 的位置。
3. 当 curr 到达链表末尾时，返回新的头节点。

递归方法：

1. 使用递归反转链表，递归的终止条件是当前节点为 null 或者 next 节点为 null。
2. 在递归过程中，将当前节点的 next 指向前一个节点，然后返回新的头节点。

C#代码实现（迭代方法）

public ListNode ReverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;
}

C代码实现（迭代方法）

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != NULL) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}

C#代码实现（递归方法）

public ListNode ReverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = ReverseList(head.next);head.next.next = head;head.next = null;return newHead;
}

C代码实现（递归方法）

struct ListNode* reverseList(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head;}struct ListNode* newHead = reverseList(head->next);head->next->next = head;head->next = NULL;return newHead;
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度。每个节点最多被访问一次。
• 空间复杂度：O(1)。除了常数级别的变量，算法的空间复杂度是常数级别的。