ARTS - Week 9

ARTS - Week 9

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 206 - Reverse Linked List

Reverse a singly linked list.

Difficulty: Easy

Example:

reverse_linked_list

Solution

第一种解法:临时保存节点的前后指针
# Python

class Solution:
    def reverseList(self, head):
        node, prev = head, None

        while node is not None:
            node.next, prev, node = prev, node, node.next

        return prev
# Ruby

def reverse_list(head)
  prev = nil
  curr = head
  while curr != nil
    prev, prev.next, curr = curr, prev, curr.next
  end
  
  return prev
end

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 36 ms.
Your runtime beats 100.00 % of python3 submissions.

Ruby:
Runtime: 44 ms.
Your runtime beats 100.00 % of ruby submissions.

第二种解法:递归

假设后面的节点已反转,那么第k个节点需要设置nk.next.next = nk;

# Python

    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return p
# Ruby

def reverse_list(head)
  return head if head.nil? || head.next.nil?
  p = reverse_list(head.next)
  head.next.next = head
  head.next = nil

  return p
end

复杂度

  • Time complexity: O(N);
  • Space complexity: O(N);

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 92.90 % of python3 submissions.

Ruby:
Runtime: 48 ms.
Your runtime beats 76.63 % of ruby submissions.


# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×