Tag Archives: LeetCode problem solving report

21. Merge Two Sorted Lists [easy] (Python)

Topic link
https://leetcode.com/problems/merge-two-sorted-lists/
The questions in the original

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

The title translation
Merge the two ordered lists and return the new list. The new list should be the result of splicing two old lists.
Thinking method
Thinking a
After merging, the linked list is still in order. Two linked lists can be traversed at the same time. Each time, the nodes with smaller values in the two lists are selected and connected in turn to obtain the final linked list.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        head = cur = ListNode(0)
        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 head.next

Idea 2
Similar idea one, you can take the linked list with a smaller head node as a reference, and insert the nodes in another linked list into the linked list according to the size, forming a large ordered linked list
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        head = small = l1 if l1.val < l2.val else l2
        big = l1 if l1.val >= l2.val else l2
        pre = None
        while big:
            if not small:
                pre.next = big
                break
            if big.val >= small.val:
                pre = small
                small = small.next
            else:
                tmp = big.next
                pre.next = big
                pre = big
                big.next = small
                big = tmp
        return head

Thought three
Let’s think recursively.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51529359

7. Reverse Integer [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-integer/
The questions in the original

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

The title translation
Reverses the number in an integer.
example 1: given x=123, return 321; Example 2: Given x=-123, return -321.

If x is equal to 10 or x is equal to 100, then both returns 1. 2. What happens to overflow after the original integer is reversed?– For example, if x=1000000003, reverse overflow, then the specified overflow results will return 0.
Thinking method
Here, Python’s handling of integers doesn’t actively overflow and actually causes problems, requiring special handling.
Thinking a
Loop through the modulus of 10 to get the tail number, step by step multiply 10 to construct a new flipped integer. However, it is important to first judge the positive and negative of the original number, and finally judge whether the result is overflow.
code

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        flag = 1 if x >= 0 else -1
        new_x, x = 0, abs(x)
        while x:
            new_x = 10 * new_x + x % 10
            x /= 10
        new_x = flag * new_x
        return new_x if new_x < 2147483648 and new_x >= -2147483648 else 0

Idea 2
Python string reversal is used to reverse an integer, and the reversed string is converted back to an integer. As above, pay attention to positive and negative and overflow situations.
code

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        x = int(str(x)[::-1]) if x >= 0 else - int(str(-x)[::-1])
        return x if x < 2147483648 and x >= -2147483648 else 0

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/52039990

206. Reverse Linked List [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-linked-list/
The questions in the original

Reverse a singly linked list.

The title translation
Flip a one-way linked list
Thinking method
This topic is relatively basic, and there are many solutions to it, and there are also many solutions to AC. Here, only part of the ideas are sorted out for reference.
Thinking a
Using the stack structure, the contents of the linked list can be pushed onto the stack in turn, and then ejected from the stack in turn to construct the reverse order. The following code emulates the stack with ordinary arrays.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = head
        newList = []
        while p:
            newList.insert(0, p.val)
            p = p.next

        p = head
        for v in newList:
            p.val = v
            p = p.next
        return head

Idea 2
Similar to the idea of a stack, but directly in the original linked list operation, by iterating the node reorganization, the previous node moved to the back of the reorganized list. It’s actually an upside-down operation.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = None
        while head:
            p = head
            head = head.next
            p.next = new_head
            new_head = p
        return new_head

Thought three
Recursion. Notice the termination condition
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        p = head.next
        n = self.reverseList(p)

        head.next = None
        p.next = head
        return n

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51306170