Let Code Day78 Starting from Zero "206. Reverse Linked List"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 77 starting from zero "1502. Can Make Arithmetic Progression From Sequence"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!

problem

206. Reverse Linked List The difficulty level is Easy.

The problem is that you just flip a given unidirectional linked list over.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

solution

For the time being, iterative things.

# 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 != None:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre
# Runtime: 44 ms, faster than 26.15% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.3 MB, less than 67.33% of Python3 online submissions for Reverse Linked List.

Prepare three variables, pre, cur, and nex, and keep the previous, current, and subsequent elements and replace them. I think you should think of it as an image of preparing variables and creating temporary escape places for each.

However, if this is the case, regardless of the scale, if the number of variables increases, the amount of processing will increase and it will be troublesome to write. After all I want to have fun.

Now, let's try using stack.

# 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:
            return None
        
        stack = []
        
        while head.next:
            stack.append(head)
            head = head.next
            
        while stack:
            cur = stack.pop()
            cur.next.next = cur
            cur.next = None
            
        return head
# Runtime: 40 ms, faster than 46.28% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.1 MB, less than 96.42% of Python3 online submissions for Reverse Linked List.

I like this one because I can write it cleanly without messing up. And a little bit, the speed has improved.

I wrote two examples of answers, but how about it?

Isn't this smarter and better? If you have an opinion, I would be grateful if you could comment.