Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/
https://leetcode.com/problems/reverse-linked-list/description/
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, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre=None
        cur=head
        while cur:
            tmp=cur.next
            cur.next=pre
            pre=cur
            cur=tmp
        return pre

Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/
https://leetcode.com/problems/reverse-linked-list-ii/
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head or not head.next or left == right:
            return head
        pre = None
        cur = head
        for _ in range(left - 1):
            pre = cur
            cur = cur.next

        l1 = pre
        tail_l2 = cur

        for _ in range(right - left + 1):
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp

        if l1:
            l1.next = pre
        else:
            head = pre

        tail_l2.next = cur

        return head

Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/
https://leetcode.com/problems/add-two-numbers-ii/
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
# 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: ListNode, l2: ListNode) -> ListNode:
        def reverse_list(lst):
            head = lst
            pre, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre

        l1, l2 = reverse_list(l1), reverse_list(l2)

        carry = 0

        l3 = ListNode(0)
        cur = l3

        while l1 or l2 or carry:
            value = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, number = divmod(value, 10)
            cur.next = ListNode(number)
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return (reverse_list(l3.next))

Robot Return to Origin

https://leetcode.com/problems/robot-return-to-origin/
https://leetcode.com/problems/robot-return-to-origin/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution1:
    def judgeCircle(self, moves: str) -> bool:
        return moves.count('U')==moves.count('D') and moves.count('L')==moves.count('R')
class Solution2:
    def judgeCircle(self, moves: str) -> bool:
        init_state=cur_state=[0,0]
        directions={
            'U':[0,1],
            'R':[1,0],
            'D':[0,-1],
            'L':[-1,0]
        }
        
        for move in moves:
            cur_state=[x+y for x,y in zip(cur_state,directions[move])]
        
        return cur_state==init_state

Robot Bounded In Circle

https://leetcode.com/problems/robot-bounded-in-circle/
https://leetcode.com/problems/robot-bounded-in-circle/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        init_state=cur_state=[0,0]
        directions={
            'N':[0,1],
            'E':[1,0],
            'S':[0,-1],
            'W':[-1,0]
        }
        directions_list=['N','E','S','W']
        direct='N'
        for i in range(len(instructions)):
            if instructions[i]=='G':
                cur_state=[x+y for x,y in zip(cur_state,directions[direct])]
            elif instructions[i]=='L':
                direct=directions_list[(directions_list.index(direct)-1) % len(directions_list)]
            elif instructions[i]=='R':
                direct=directions_list[(directions_list.index(direct)+1) % len(directions_list)]
        return init_state==cur_state or direct!='N'

思考：为什么要索引值要与方向列表长度做模运算？

Python 中的索引操作是循环的。当索引值是负数时，Python 会从列表的末尾开始向前计数。例如，对于列表 directions_list 的长度为 4，索引值范围是 0 到 3。如果执行 directions_list.index('W')-1，3-1=2，这是有效的索引值。

但是，如果执行 directions_list.index('N')-1，0-1=-1，这就是一个无效的索引值。在 Python 中，这样的索引值将被解释为从列表末尾开始计数，即最后一个元素。所以 -1 实际上指向列表 directions_list 的最后一个元素 ‘W’。

为了避免这种情况，我们使用 % len(directions_list) 进行调整。它可以将负数索引值转换为等效的正数索引值，确保索引操作始终在有效范围内。对于上述例子，0-1 根据 % len(directions_list) 变为 3，得到正确的索引值。

快来参与讨论吧~