class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 首先对特殊情况进行处理，l1 l2 为空的时候
        if not (l1 and l2) : # 这个表达式的意思只要l1 l2 不全为真就符合条件
            return l1 or l2 
        elif l1.val > l2.val:  # 判断哪一个值比较小，然后保留哪一项 
            l2.next = self.mergeTwoLists(l2.next,l1)  # 递归思想的精髓
            return l2  # 返回小的这一项
        else :
            l1.next = self.mergeTwoLists(l1.next,l2) 
            return l1
# 注意：l1 l2 表示的不是整个链表，而只是每一个结点

# 这个是别人给的题解，大佬写的很好。
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2: # 判断l1 是否为空
            if l1.val > l2.val : l1,l2 = l2,l1 # 始终让l1 为小值
            l1.next = self.mergeTwoLists(l1.next,l2) # 递归的精髓 
        return l1 or l2

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head :return head # 首先判断链表是否为空，若为空直接返回
        head1 = head
        l = [] # 定义一个空的列表 用来存放已经遍历过的链表结点
        l.append(head.val) # 将遍历过的链表结点添加进入列表中
        while head and head.next: # 当前结点和下一个结点都为真继续
            if head.next.val in l : # 若下一节点的值已经在列表中
                head.next = head.next.next # 进行删除操作，跳过下一节点，直接指向下下结点
            else:
                l.append(head.next.val) # 将结点添加进入列表
                head = head.next # 进行遍历
        return head1 # 返回删除重复元素后的链表

# 解题思路；利用快慢指针，一个指针快，另一个慢，若链表有环，则总有相遇的时候
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next : # 若链表中没有元素，或者只有一个元素，则不可能成环
            return False
        fast = head
        slow = head
        while fast:
            if fast.next == None: # 若快指针可以走到头，则肯定没有环
                return False
            else :
                fast = fast.next.next # 快指针每次走两步
                slow = slow.next # 慢指针走一步
            if slow == fast: # 当快慢指针相遇
                return True
        return False # 当快指针为None时退出

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB: # 若两个链表中其中一个链表为空则不可能相交
            return None
        length1 = 0 # 用来接收headA链表的长度
        length2 = 0
        h1 = headA
        h2 = headB
        while h1: # 遍历链表算出两个链表的长度
            length1 += 1
            h1 = h1.next
        while h2:
            length2 += 1
            h2 = h2.next
        if length1 > length2: # 让比较长的链表先走
            for i in range(length1 - length2):
                headA = headA.next
        elif length1 < length2:
            for i in range(length2 - length1):
                headB = headB.next
        while headA: # 现在两个指针处于同一位置
            if headA == headB: # 判断是否为同一节点
                return headA
            headA = headA.next
            headB = headB.next
        return None

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if not head:return head # 判断是否为空链表
        head1 = head # 用head1返回新的链表
        while head: # 找到第一个不需要删除的链表
            if head.val == val: # 需要删除时，将head1等于head的下一节点
                head1 = head.next
                head = head.next
            else:
                break
        while head and head.next: # 进行链表的遍历，进行删除所给的元素
            if head.next.val == val:
                head.next = head.next.next
            else :
                head = head.next
        return head1 # 返回新的链表

# 用快慢指针的方法找到链表的中间节点，然后将后半段链表进行反转，在判断
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next : # 若链表为空或为一个元素，则链表为回文链表
            return True
        fast = head
        slow = head # 快慢指针 快指针走两步，慢指针走一步
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow  # 此时slow为中点指针
        pre = None
        # 将后半段链表表反转
        while slow:
            slow.next,pre,slow = pre,slow,slow.next 
            # 不可以分开写成三个语句，Python特有，在C语言中这样写是错误的
            # 他们这三个语句的执行是相同，没有先后之分。
        # 此时后半段列表的头指针为pre
        while head != mid:
            if head.val != pre.val:
                return False
            pre = pre.next
            head = head.next
        return True