I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)

Introduction

@Ishishow is running a free English word site E-tan.

I would like to work on letcode every day to improve my ability as a programmer and give my own way of solving it.

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to Go language + algorithm I will solve it with Golang and Python to strengthen my brain. (Python is weak but experienced)

7th question (problem 21)

  1. Merge Two Sorted Lists

--Problem content (Japanese translation)

Merges two sorted linked lists and returns them as a new ** sorted ** list. The new list must be created by joining the nodes of the first two lists together.

Example 1:

img

  Input: l1 = [1,2,4], l2 = [1,3,4]
  Output: [1,1,2,3,4,4]

Example 2:

  Input: l1 = [], l2 = []
  Output: []

Example 3:

  Input: l1 = [], l2 = [0]
  Output: [0]

Way of thinking

  1. Create a new ListNode
  2. Pass the created ListNode reference to a variable called res
  3. Turn the loop, advance the smaller val of l1 and l2, and assign it to cur.
  4. When either one goes to the end point, the loop ends, so substitute the rest.
  5. return is res. Since it is 0 at first, it starts from the next.

--Answer code

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        cur = ListNode(0)
        res = cur
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return res.next  

--I'll write it in Go too!

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	cur := &ListNode{}
	res := cur
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	} else if l2 != nil {
		cur.Next = l2
	}

	return res.Next
}

Recommended Posts

I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
Let Code Day24 Starting from Zero "21. Merge Two Sorted Lists"
I tried Grumpy (Go running Python).
I tried running faiss with python, Go, Rust
I tried Python> decorator
I tried fp-growth with python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried to touch Python (installation)
I tried web scraping with python.
I tried using Thonny (Python / IDE)
I tried running prolog with python 3.8.2.
I tried Line notification in Python
I tried SMTP communication with Python
[Python] I tried using YOLO v3