PeterQwQ
0%

发表于

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans, stack = [], []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                ans.append(root.val)
                root = root.right
        return ans

发表于

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

创建一个字典，将链表节点和节点值对应起来，然后对字典进行排序，最后根据排序后的字典创建新的链表，返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return
        dic = {}
        cur = head
        while cur:
            dic[cur] = cur.val
            cur = cur.next
        sorted_dic = sorted(dic.items(), key=lambda x: x[1])
        
        new_head = ListNode(sorted_dic[0][1])
        cur = new_head
        for i in range(1, len(sorted_dic)):
            cur.next = ListNode(sorted_dic[i][1])
            cur = cur.next
        return new_head

发表于

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。你的任务是 深拷贝 这个链表，并返回新链表的头指针。你的代码 只 接受原链表的头节点 head 作为传入参数。

这个题目的主要难点在于如何处理 random 指针，因为 random 指针可能指向任意节点，所以我们需要一个字典来存储原链表节点和新链表节点的对应关系。通过这个字典，我们可以很容易的找到 random 指针指向的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return
        dic = {}
        current = head
        while current:
            dic[current] = Node(current.val)
            current = current.next
        current = head
        while current:
            dic[current].next = dic.get(current.next)
            dic[current].random = dic.get(current.random)
            current = current.next
        return dic[head]

发表于

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

用哨兵节点dummy，然后每次交换两个节点，然后移动到下一组节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head
        current = dummy

        while current.next and current.next.next:

            first = current.next
            second = current.next.next

            current.next = second
            first.next = second.next
            second.next = first

            current = first

        return dummy.next

发表于

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

找到链表的倒数第 n 个节点，然后删除该节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        count = 0
        current = head
        while current:
            count += 1
            current = current.next
        pos = count - n
        index = 0
        current = head

        if pos == 0:
            return head.next

        while current:
            index += 1
            if index == pos and current.next is not None:
                current.next = current.next.next
                break
            else:
                current = current.next
        return head

发表于

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

模拟这个列表的过程，将两个链表的数字取出来，相加，然后再转换成链表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1_nums, l2_nums = [], []
        
        while l1:
            l1_nums.append(l1.val)
            l1 = l1.next

        while l2:
            l2_nums.append(l2.val)
            l2 = l2.next

        l1_nums = l1_nums[::-1]
        l2_nums = l2_nums[::-1]  
        n = int(''.join(map(str, l1_nums))) + int(''.join(map(str, l2_nums)))
        head = ListNode(n%10)
        current = head
        n = n // 10

        while n:
            val = n % 10
            new_node = ListNode(val)
            current.next = new_node
            current = current.next
            n = n // 10
        return head

发表于

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

直接写就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        if list1 is None and list2 is None:
            return None
        if list1 is None and list2 is not None:
            return list2
        if list1 is not None and list2 is None:
            return list1

        if list1.val <= list2.val:
            ans = ListNode(list1.val)
            list1 = list1.next
        else:
            ans = ListNode(list2.val)
            list2 = list2.next

        current = ans
        while list1 and list2:
            if list1.val <= list2.val:
                new_node = ListNode(list1.val)
                current.next = new_node
                list1 = list1.next
            else:
                new_node = ListNode(list2.val)
                current.next = new_node
                list2 = list2.next
                
            current = current.next
        if list1: current.next = list1
        if list2: current.next = list2
        return ans

发表于

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null 。不允许修改链表。

和环形链表 I 一样的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head is not None:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
        return None

发表于

给你一个链表的头节点 head ，判断链表中是否有环。

用一个 set 存储已经遍历过的节点，如果遍历到的节点已经在 set 中，说明链表有环。如果没有环，遍历到 None 时退出循环返回 False。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head is not None:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

发表于

给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表。如果是，返回 true ；否则，返回 false 。

用一个 nums 数组存起来链表的值，然后双指针判断是否是回文链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        nums = []
        while head is not None:
            nums.append(head.val)
            head = head.next
        n = len(nums)
        if n == 1 or n == 0:
            return True
        i, j = 0, n-1
        while i <= j:
            if nums[i] == nums[j]:
                i += 1
                j -= 1
                continue
            else:
                return False
        return True