单链表反转：Python/Java/C++三解

LeetCode206

给你单链表的头节点head，请你反转链表，并返回反转后的链表。

示例一

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

Python解法

1.数组翻转

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None temp = [] while head: temp.append(head.val) head = head.next dummy = ListNode() p = dummy for num in reversed(temp): p.next = ListNode(num) p = p.next return dummy.next

2.迭代（原地翻转）

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre = None cur = head while cur: # 先保存下一个节点，防止断链 nxt = cur.next # 翻转当前节点指向 cur.next = pre # 双指针后移 pre = cur cur = nxt # pre最后是新头节点 return pre

3.递归

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 终止条件：空节点/最后一个节点 if not head or not head.next: return head # 递归拿到后半段反转后的头 new_head = self.reverseList(head.next) # 翻转当前节点与后节点的指针 head.next.next = head head.next = None return new_head

Java解法（只展示后两种）

1.迭代

class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode nxt = cur.next; // 暂存下一个 cur.next = pre; // 反转指向 pre = cur; // pre后移 cur = nxt; // cur后移 } return pre; } }

2.递归

class Solution { 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++解法

1.迭代

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

2.递归

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