日拱两卒（八）

30#

两两交换链表中的节点。

和K个一组翻转没区别。

1
class Solution:
2
    def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        cur = head
4
        pre = None
5

6
        while cur:
7
            nxt = cur.next
8
            cur.next = pre
9
            pre = cur
10
            cur = nxt
11

12
        return pre
13

14
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
15
        dummy = ListNode(0, head)
16

17
        cur = dummy.next
18
        cur_head = cur
19
        pre_cur_head = dummy
20
        cnt = 0
21

22
        while cur:
23
            cnt += 1
24
            nxt = cur.next
25
            if cnt >= 2:
26
                cur.next = None
27
                new_head = self.reverse(cur_head)
28
                cur_head.next = nxt
29
                pre_cur_head.next = new_head
30

31
                pre_cur_head = cur_head
32
                cur_head = nxt
33
                cnt = 0
34

35
            cur = nxt
36

37
        return dummy.next

29#

删除链表的倒数第N个节点。

尺子一开始左端点在链表头，右端点在正数第N个，那么尺子右端点在链表尾时，左端点就在倒数第N个。

删除其实是要找第N+1个。

1
class Solution:
2
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
3
        left = right = dummy = ListNode(0, head)
4

5
        for _ in range(n):
6
            right = right.next
7
        while right.next:
8
            left = left.next
9
            right = right.next
10
        left.next = left.next.next
11

12
        return dummy.next

28#

两数相加。

简单模拟。

1
class Solution:
2
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
3
        dummy = ListNode(0, None)
4

5
        carry = 0
6
        cur = dummy
7
        while l1 or l2:
8
            val = carry
9
            val += l1.val if l1 else 0
10
            val += l2.val if l2 else 0
11
            new_node = ListNode(val % 10, None)
12
            cur.next = new_node
13
            carry = val // 10
14

15
            cur = cur.next
16
            l1 = l1.next if l1 else l1
17
            l2 = l2.next if l2 else l2
18

19
        if carry:
20
            new_node = ListNode(carry, None)
21
            cur.next = new_node
22

23
        return dummy.next

27#

合并两个有序链表。

之前合并K个也做过了。

1
class Solution:
2
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3
        dummy = ListNode(0, None)
4

5
        cur = dummy
6
        while list1 and list2:
7
            if list1.val < list2.val:
8
                cur.next = ListNode(list1.val, None)
9
                list1 = list1.next
10
            else:
11
                cur.next = ListNode(list2.val, None)
12
                list2 = list2.next
13
            cur = cur.next
14

15
        if list1:
16
            cur.next = list1
17
        else:
18
            cur.next = list2
19

20
        return dummy.next

26#

环形链表II。

找环的第一个节点。题解太诡异了，完全不如直接哈希。

1
class Solution:
2
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        mp = {}
4

5
        while head:
6
            if mp.get(head):
7
                return head
8
            mp[head] = True
9
            head = head.next
10

11
        return None

25#

环形链表。

快慢指针看是否相遇以判环。

1
class Solution:
2
    def hasCycle(self, head: Optional[ListNode]) -> bool:
3
        slow = head
4
        fast = head
5
        while fast and fast.next:
6
            slow = slow.next
7
            fast = fast.next.next
8
            if slow == fast:
9
                return True
10
        return False

24#

回文链表。

把后半段翻转，逐位比对。

1
class Solution:
2
    def middle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        slow = head
4
        fast = head
5
        while fast and fast.next:
6
            slow = slow.next
7
            fast = fast.next.next
8
        return slow
9

10
    def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
11
        cur = head
12
        pre = None
13

14
        while cur:
15
            nxt = cur.next
16
            cur.next = pre
17
            pre = cur
18
            cur = nxt
19

20
        return pre
21

22

23
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
24
        if head.next is None:
25
            return True
26
        head2 = self.reverse(self.middle(head))
27
        while head and head2:
28
            if head.val != head2.val:
29
                return False
30
            head = head.next
31
            head2 = head2.next
32
        return True

23#

反转链表。

因为倒着做，前面用过很多次了。

1
class Solution:
2
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        pre = None
4
        cur = head
5
        while cur:
6
            nxt = cur.next
7
            cur.next = pre
8
            pre = cur
9
            cur = nxt
10
        return pre

22#

相交链表。

没想到题解这种思路，相当于两条路都走两遍的话肯定能找到。

1
class Solution:
2
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
3
        p = headA
4
        q = headB
5
        while p is not q:
6
            p = p.next if p else headB
7
            q = q.next if q else headA
8
        return p

21#

搜索二维矩阵II。

矩阵满足每行递增，每列递增，搜有无目标值。

每次看右上角能杀掉一行或一列。

1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        n, m = len(matrix), len(matrix[0])
4
        i, j = 0, m - 1
5
        while i <= n - 1 and j >= 0:
6
            if matrix[i][j] == target:
7
                return True
8
            if matrix[i][j] > target:
9
                j -= 1
10
            if matrix[i][j] < target:
11
                i += 1
12

13
        return False