编程原理：合并链表

Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

# 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: ListNode, list2: ListNode) -> ListNode:
        dummy=ListNode(0)
        cur=dummy
        while list1 and list2:
            if list1.val>list2.val:
                cur.next=list2
                cur=list2
                list2=list2.next
            else:
                cur.next=list1
                cur=list1
                list1=list1.next
        if list1 or list2:
            cur.next=list1 if list1 else list2
        return dummy.next

疑问

我有一个疑问，快慢指针的初始化，有一种是将快指针初始化为head，另一种是初始化为head.next，到底哪一种对呢，还是两种都可以，但是后面需要注意边界情况呢？

比如说那两道题来作比较：

head

https://leetcode.com/problems/palindrome-linked-list/

创建一个空的哑节点（dummy node）。这个哑节点的作用是反转链表的后半部分，以便进行回文判断。

# 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: ListNode) -> bool:
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        dummy=None
        while slow:
            tmp=slow.next
            slow.next=dummy
            dummy=slow
            slow=tmp
        left=head
        right=dummy
        while left and right:
            if left.val!=right.val:
                return False
            left=left.next
            right=right.next
        return True

head.next

https://leetcode.com/problems/sort-list/

# 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: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        slow=fast=head
        
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        
        center=slow.next
        slow.next=None

        left=self.sortList(head)
        right=self.sortList(center)
        
        dummy=ListNode(0)
        cur=dummy

        while left and right:
            if left.val<right.val:
                cur.next=left
                left=left.next
            else:
                cur.next=rigth
                right=right.next
            cur=cur.next

        cur.next=left or right

        return dummy.next

两种初始化方式

fast = head.next slow = head (这样初始化后如果链表长度为奇数，最终slow指向的是当前链表的正中间位置上的结点，如果链表长度为偶的话，则指向中间偏左的那个结点)
fast = head slow = head (这样初始化后如果链表长度为奇数，最终slow指向的是当前链表的正中间位置上的结点，如果链表长度为偶的话，则指向中间偏右的那个结点)

注意两个的区别，看题目要求来选择快慢指针的初始化方式

Merge Strings Alternately

https://leetcode.com/problems/merge-strings-alternately/

class Solution1:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        res = ""
        length = min(len(word1), len(word2))
        for index in range(length):
            res += word1[index] + word2[index]
        res += word1[length:] + word2[length:]
        return res

class Solution2:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        res = "".join(w1 + w2 for w1, w2 in zip(word1, word2))
        length_word1 = len(word1)
        length_word2 = len(word2)
        if length_word1 > length_word2:
            res += word1[-(length_word1 - length_word2):]
        elif length_word1 < length_word2:
            res += word2[-(length_word2 - length_word1):]
        else:
            res = res
        return res

s1 = Solution1()
s2 = Solution2()
while True:
    word1 = input("word1: ")
    word2 = input("word2: ")
    print(s1.mergeAlternately(word1, word2), s2.mergeAlternately(word1, word2))

Find the Difference

https://leetcode.com/problems/find-the-difference/

from collections import Counter

class Solution1:
    def findTheDifference(self, s: str, t: str) -> str:
        # 使用count
        for item in t:
            if s.count(item) != t.count(item):
                return item

class Solution2:
    def findTheDifference(self, s: str, t: str) -> str:
        dict_s = Counter(s)
        dict_t = Counter(t)
        for item in t:
            if dict_s[item] != dict_t[item]:
                return item

s1 = Solution1()
s2 = Solution2()
while True:
    s = input("s: ")
    t = input("t: ")
    print(s1.findTheDifference(s, t), s2.findTheDifference(s, t))

Find the Index of the First Occurrence in a String

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

class Solution1:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.index(needle) if needle in haystack else -1

class Solution2:
    def strStr(self, haystack: str, needle: str) -> int:
        length_haystack = len(haystack)
        length_needle = len(needle)

        for i in range(length_haystack - length_needle + 1):
            for j in range(length_needle):
                if needle[j] != haystack[i + j]:
                    break
                if j == length_needle - 1:
                    return i
        return -1

class Solution3:
    def strStr(self, haystack: str, needle: str) -> int:

        length_haystack = len(haystack)
        length_needle = len(needle)

        if length_haystack < length_needle or needle not in haystack:
            return -1
        if not needle:
            return 0
        left_index = 0
        rigth_index = 0

        while left_index <= length_haystack - length_needle:
            right_index = left_index + length_needle
            if haystack[left_index:right_index] == needle:
                return left_index
            else:
                left_index += 1

        return -1

s1 = Solution1()
s2 = Solution2()
s3 = Solution3()
while True:
    haystack = input("haystack: ")
    needle = input("needle: ")
    print(s1.strStr(haystack, needle), s2.strStr(haystack, needle), s3.strStr(haystack, needle))