LeetCode

Appearance

206. Reverse Linked List ​

题目 ​

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

Constraints:

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Related Topics
  • 递归
  • 链表

  • 👍 3901
  • 👎 0

    • 思路 ​

    反转链表的经典题目，本题采用双指针法，还有递归法可实现，后面补充

    解法 ​

        def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None

        while cur:

            temp = cur.next
            cur.next = pre

            pre = cur

            cur = temp

        return pre

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(1)

    递归解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        return self.resverse(None, head)


    def resverse(self, pre:[ListNode], cur:Optional[ListNode]):
        temp = cur.next
        cur.next = pre
        if not temp:
            return cur

        return  self.resverse(cur, temp)


        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)