21. 合并两个有序链表

将两个升序链表合并成新的升序链表，只需要创建一个新的链表，把两个指针分别放到链表A和链表B的头部，然后不停的比较哪个值更小就加入到新的链表前面，然后指针后移一位即可。直到有一个链表为空。循环结束。然后看那个链表不为空还有元素，直接接到新链表即可。

# 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: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # 使用虚拟头节点，简化问题。
        dummy = ListNode(-1)
        head = dummy
        # 不停比较两个元素当前指向位置的元素大小，然后添加到新列表
        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
        # 如果有链表依然不为空，直接添加到新链表即可。
        if list1 is not None:
            head.next = list1
        if list2 is not None:
            head.next = list2
        return dummy.next

86. 分隔链表

这个题让我们把一个链表进行分割，小于x的节点都出现在大于等于x的节点之前，并且保持节点的相对位置不变。我们可以创建两个新的链表D1和D2,然后遍历题目输入的链表，如果值小于x，就接到D1后面，否则就接到D2后面，一轮遍历之后，D1链表就是所有值小于x的节点，D2链表就是值大于等于x的节点。并且我们从前往后遍历，相对顺序自然是不变的，然后把D2链表接到D1链表后面，也就完成了题目的需求。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 创建两个虚拟头节点。
        dummy1 = ListNode(-1)
        dummy2 = ListNode(-1)
        head1, head2 = dummy1, dummy2
        # 遍历链表
        while head is not None:
            # 如果值小于x就接到D1后面，否则就接到D2后面
            if head.val < x:
                head1.next = head
                head1 = head1.next
                head = head.next
                head1.next = None
            else:
                head2.next = head
                head2 = head2.next
                head = head.next
                head2.next = None
        # 把D2链表接到D1链表后面即可
        head1.next = dummy2.next
        return dummy1.next

23. 合并 K 个升序链表

这个和合并两个链表有异曲同工之妙，只不过把比较两个链表头部的值，变成了比较N个链表头部的值。每次取出最小的接到新的链表后面即可。但是比较N个就不能单纯的手写if else来比较，需要用到最小堆。元素存进去之后，每次弹出的元素就是最小的，非常符合我们现在的需求。至于为什么存（节点的值，链表次序，节点）这样的三元组，我们首先肯定要存这个节点node，但是类和类之间是不能比较的，所以要把这个节点的值放进去。然后最小堆排序的规则是元组里的第一个元素进行比较，如果第一个元素相同就依次比较后面的元素，如果两个节点的值相同，那么就又回到了类不能比较的问题，所以要在节点的值和节点直接再放一个链表的次序。而次序是递增的，一定能比较出大小。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        h = dummy
        pq = []
        for i, node in enumerate(lists):
            if node is not None:
                heapq.heappush(pq, (node.val, i, node))
        while pq:
            val, i, node = heapq.heappop(pq)
            h.next = node
            h = h.next
            if node.next is not None:
                heapq.heappush(pq, (node.next.val, i, node.next))
        return dummy.next

19. 删除链表的倒数第 N 个结点

这个题需要用到一个小技巧，怎么找链表的倒数第N个节点呢？遍历一遍看看链表多长，第二次自然就找到了，但是这样就比较麻烦了。那有没有什么便捷的办法，有的兄弟有的。设置一个p1指针指向头节点走n步，然后再设置一个p2指针指向头节点，然后p1和p2同时前进，当p1为空的时候，p2就在倒数第n个节点的地方了。这个其实不难理解，相当于p2比p1少走了n步，p1是走了整个链表，p2自然就是停留在倒数第n个节点了。

这个题只需要很小的一个变化，因为我们要删除倒数第N个节点，那就要找到第N+1个节点，然后修改指针删除就可以了。然后这个题依然需要用到非常好用的虚拟头节点技巧，避免找倒数n+1个节点越界，或者删除之后链表为空等特殊情况。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        p1 = dummy
        p2 = dummy
        for i in range(n + 1):
            p1 = p1.next
        while p1 is not None:
            p1 = p1.next
            p2 = p2.next
        p2.next = p2.next.next
        return dummy.next

876. 链表的中间结点

这个题使用直观的想法就是，先遍历一遍链表算出总长度，第二遍遍历一半就找到中点了。但是有更加高效的写法，使用快慢双指针，设置两个指针slow和fast，初始都指向头结点，fast一次走两步，slow一次走一步，当fast走到头，slow就停在中间了。相当于fast走了整个链表，slow走了它的一半，就是中点了。

如果链表的长度是偶数，也就是中点有两个的时候，这个解法求的是后面的那个节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

141. 环形链表

这个题也是使用876题的快慢双指针就可以解决了。设置一快一慢两个指针，如果快的指针追上慢指针了，说明链表里面是有环的，如果快指针走到头了也没和慢指针相遇，那就是没有环。

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


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast != None and slow != None:
            if fast.next != None:
                fast = fast.next.next
            else:
                return False
            slow = slow.next
            if fast == slow:
                return True
        return False

142. 环形链表 II

这个题是141题的进阶版，有点不太好解释，假如slow和fast相遇的时候，slow走了k步，fast走了2k步，fast比slow多走的k步就是在环里转圈，所以k一定是环长度的整数倍。假如相遇点距离环起点的长度是m，那么从头节点到环起点就是k-m，然后fast多走了k步，同样减去这个m，距离也是能走到环起点。简单来讲的话，就是先找到slow和fast相遇的节点，然后让slow再次指向头节点，然后和fast同速进行。相遇的节点就是环起点了。

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


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if fast == None or fast.next == None:
            return None
        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

160. 相交链表

简单的想分别从头指针往后遍历看是否有相同节点就行了，但是这个题要用到对齐的思想，因为A链表和B链表的长度可能是不一样的，把A链表拼到B后面，把B链表拼到A后面，这两个链表长度就相同了。

例如链表A是 a1->a2->c1->c2

链表B是b1->b2->b3->c1->c2

对齐效果就是这样：就可以找到共同的节点c1了。如果是没有共同节点的情况。p1和p2都走到None也会相等跳出循环，返回的是一个None，也是符合题目条件的，也就是没有相交点返回None。

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p1,p2=headA,headB
        while p1!=p2:
            if p1 is None:
                p1=headB
            else:
                p1=p1.next
            if p2 is None:
                p2=headA
            else:
                p2=p2.next
        return p1