剑指OfferII024.反转链表

---

comments: true edit_url: github /doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20024.%20%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/README.md 剑指 Offer II 024. 反转链表 题目描述

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

 

示例 1：

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

示例 2：

输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

 

提示：

链表中节点的数目范围是 [0, 5000]-5000 <= Node.val <= 5000

 

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

 

注意：本题与主站 206 题相同：  leetcode /problems/reverse-linked-list/

解法 方法一:三指针 Python3 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: pre,cur=None,head while cur: nxt=cur.next cur.next=pre pre=cur cur=nxt return pre Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null, p = head; while (p != null) { ListNode q = p.next; p.next = pre; pre = p; p = q; } return pre; } } C++ /** * 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 = nullptr; ListNode* p = head; while (p) { ListNode* q = p->next; p->next = pre; pre = p; p = q; } return pre; } }; Go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { var pre *ListNode for p := head; p != nil; { q := p.Next p.Next = pre pre = p p = q } return pre } JavaScript /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { let pre = null; for (let p = head; p; ) { let q = p.next; p.next = pre; pre = p; p = q; } return pre; }; C# /** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode ReverseList(ListNode head) { ListNode pre = null; for (ListNode p = head; p != null;) { ListNode t = p.next; p.next = pre; pre = p; p = t; } return pre; } } Swift /** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init(_ val: Int) { * self.val = val * self.next = nil * } * } */ class Solution { func reverseList(_ head: ListNode?) -> ListNode? { var prev: ListNode? = nil var current = head while current != nil { let next = current?.next current?.next = prev prev = current current = next } return prev } } 方法二:递归

1）res = reverseList(head.next): 作用体现在框里（抽象） 2）head.next.next=head,head.next=none:体现在最前一段反转

python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: #返回反转后的链表的头节点 if not head or not head.next:return head res=self.reverseList(head.next) head.next.next=head head.next=None return res Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode res = reverseList(head.next); head.next.next = head; head.next = null; return res; } }