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