LeetCode 206. Reverse Linked List - 链表(Linked List)系列题7

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

Example 1:

LeetCode 206. Reverse Linked List - 链表(Linked List)系列题7

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

Example 2:

LeetCode 206. Reverse Linked List - 链表(Linked List)系列题7

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?

题目要求反转一个链表,并要求分别用迭代法和递归法解答。

迭代法:基本思路就是遍历整个链表,让当前节点next指向其父节点。用两个指针实现颠倒顺序,一个指针指向当前节点,另一个指针指向当前节点的父节点(一开始当前节点是头节点则其父节点为空)。在一个循环里,先暂存当前节点的子节点,然后让当前节点next指向其父节点,父节点指针更新为当前节点,当前节点指针更新为之前暂存的子节点,进入下一个循环,直到当前节点为空。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        return pre

递归法:首先看递归可行性,把链表分成第一个节点和剩余部分,如果剩余部分可以被反转,那么只要把剩余部分反转后的最后一个节点的next指向第一个节点,第一个节点的next指向空,就实现了整个链表的反转。然后判断递归的终止条件,当剩余部分只剩一个节点时,就可以不用处理因为头和尾都是自身节点。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return newHead

上一篇:c++11新特性正则匹配


下一篇:ROS2--Action