写在前面：

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

# 调用
new_list = ListNode(0)

---

1290. Convert Binary Number in a Linked List to Integer <倒序>

我做链表的第一道题：

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        n = 0
        total = 0
        plist = []
        
        while(head):
            n += 1
            if head.val == 1:
                plist.append(n)
            head = head.next
        
        for x in plist:
            total += pow(2,n-x) 
            print(n,total)
            
        return total

中心思想是要把给的head倒过来计算。有两种比较直接的思路：首先就是一一存出来倒着算，当然还有一种类似的看有人读了一遍长度，再重新读了一遍链表直接算；第二种就是把需要加的index记下来单独拿出来算。我写的是第二种思路。
如果对链表和python的指针不熟，比如像我现在这样，这题的重点就是从非常浅的层次来告诉你head.val == 1、head = head.next，以及直接从链表下手能干什么不能干什么。

---

<Floyd龟兔系列>

876. Middle of the Linked List

明明可以简单做的一道题，翻了很久discussion有绝妙的感悟。还记得大二数据结构课老师讲的检测loop吗！这个快慢指针思想就是可以放进去。放一下快慢指针最经典的用法 ：

141. Linked List Cycle

def hasCycle(self, head):
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

142. Linked List Cycle II

追加一道题，除了判断是否是环以外，还有确定起点的位置。需要用到Floyd算法的思想：

• 确定有环：slow和fast相遇
• 确定起点的位置：一个在起点一个在相遇点，一次一步，相遇点即为起点。
  参考代码：

def detectCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
    while head != slow:
        slow = slow.next
        head = head.next
    return head

comeback 回到876这道题（求中点），相当于一个快一倍的指针fast和一个正常的指针slow。slow刚好就是指向一半的水平：

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

160. Intersection of Two Linked Lists

变形有点多， 这个题应该是实现了功能的，但是没有检查输出是否符合要求，看个思路：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB: return None
        # 1 - concate A and B
        last = headA
        while last.next: last = last.next
        last.next = headB
        
        # 2 - slow & fast -> check loop and find the intersections:
        slow = fast = headA
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = headA
                break
        else:
            return None
        while fast != slow:
            slow = slow.next
            fast = fast.next
        return slow

234. Palindrome Linked List

这个题一定要加在这个大类里面分享一下！！细想回文其实是mid的部分应用，加上反转链表两个部分。如果说一个链表有奇数位，那一定不是回文了；如果是偶数位，有可能是回文。思路其实就是前半段和后半段去一一匹配，如果都能匹配上那么就是回文。答案参照discussion区的一个大佬回答，代码稍微整理贴在下面。但是我在LC上跑不过，说是时间超了。anyway，不管那么多，我是支持这个思路的。

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        reverse = None
        while fast and fast.next:
            reverse = slow
            reverse.next = reverse
            slow = slow.next
            fast = fast.next.next
        
        if fast is None:
            return False
        else:
            slow = slow.next
            while slow.val == reverse.val:
                slow = slow.next
                reverse = reverse.next
            return not slow

---

<删除点系列>

237. Delete Node in a Linked List

这个题要注意看下最上面注释给的ListNode的标准写法。说白了人要的也不多，就是要一个node.val和node.nextd的定义。也不难。

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

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

1474. Delete N Nodes After M Nodes of a Linked List

算是237的一个follow-up。但是因为定义的对象是原本给的Linklist， 而不是上题的那个Node，所以定义过程不至于这么麻烦。主要就是操纵指针的位置。
这题我在解的时候用了两个指针：p和post。其中post就一直在后面观望，因为考虑到我们进了删除的列m还没结束之前就已经到最后一位了

class Solution:
    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        p = head
        post = head 
        countm = m
        countn = n
        while p:
            if countm != 0:                      # 1.判断是正常位还是要删的位
                countm -= 1
                post = p
                p = p.next
            else:
                if countn != 0:                  # 2.判断删除位是否到头
                    print("delete",p.val)
                    if p.next is None:           # 最后一位
                        post.next = None
                    p = p.next
                    countn -= 1
                else:
                    post.next = p
                    countn = n
                    countm = m
    
        return head
                

83. Remove Duplicates from Sorted List

看起来是去重，实际上是一个道理。少用多余的指针，而是用简单的.next.next这种表达方式解决问题。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            if cur.next.val != cur.val:
                cur = cur.next
            else:
                cur.next = cur.next.next
                
        return head

---

21. Merge Two Sorted Lists

这绝对是熟悉链表的好题：
重点就是抓住我一开始给的那个模板，我们先声明一个新链表。特别的是这个开头p指向的第一位是0，所以最后返回新链表l的时候要return l.next。整体类似于两个指针对l1和l2当前指的位一一比较，小的被解开并接到原来的表后面。因为不是在复制字串，所以不用去声明赋值之类的东西。

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l = ListNode(0)
        p = l
        while l1 and l2:
            if l1.val <= l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        p.next = l1 or l2
        
        return l.next

---