单向链表中有n个节点，时间复杂度为O(1)的算法有哪些

单向链表中有n个节点，时间复杂度为O(1)的算法有以下几种：

1. 查找链表的尾节点：由于单向链表只能从前往后遍历，如果要查找尾节点，需要遍历整个链表，时间复杂度为O(n)。但是，可以在链表的构建过程中将尾节点保存下来，这样就可以在O(1)的时间内访问尾节点。

2. 在链表头部插入节点：在单向链表的头部插入节点，只需要将新节点的指针指向原头节点，然后将头节点指向新节点即可，时间复杂度为O(1)。

3. 在链表尾部插入节点：如果在单向链表的尾部插入节点，需要遍历整个链表才能找到尾节点，时间复杂度为O(n)。但是，可以在链表的构建过程中将尾节点保存下来，这样就可以在O(1)的时间内访问尾节点，然后将新节点插入到尾节点之后即可，时间复杂度为O(1)。

4. 删除链表头部节点：在单向链表的头部删除节点，只需要将头节点指向下一个节点即可，时间复杂度为O(1)。

5. 判断链表是否为空：在单向链表中，只需要判断头节点是否为NULL即可判断链表是否为空，时间复杂度为O(1)。

需要注意的是，虽然以上算法的时间复杂度为O(1)，但是其实现的前提条件是：在链表的构建过程中保存了头节点和尾节点。如果没有保存头节点和尾节点，或者需要在中间插入或删除节点，时间复杂度就不再是O(1)了。

相关问题

将n个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找

对于采用二分查找的情况，首先需要明确链表中数据已经按照从小到大的顺序排列好。二分查找是一种高效的查找算法，可以在有序序列中快速定位目标值。

在二分查找过程中，需要设定一个左边界和一个右边界，初始时左边界指向链表的第一个节点，右边界指向链表的最后一个节点。然后，通过比较目标值和中间节点的值，缩小查找范围。

具体操作如下：
1. 计算链表长度，得到总节点数m。
2. 初始化左边界为第一个节点，右边界为最后一个节点，中间节点为第(m+1)/2个节点。
3. 以目标值与中间节点的值进行比较：
- 若目标值等于中间节点的值，则找到目标值。
- 若目标值大于中间节点的值，则目标值可能在中间节点的右侧，更新左边界为中间节点的下一个节点。
- 若目标值小于中间节点的值，则目标值可能在中间节点的左侧，更新右边界为中间节点的前一个节点。
4. 重复步骤3，直到找到目标值或左边界大于右边界为止。

由于链表的特殊结构，无法通过索引直接访问某个节点，需要通过指针来遍历链表。每次查找的时间复杂度为O(logn)，总共需要遍历logn次，因此二分查找的时间复杂度为O(logn)。

需要注意的是，由于链表查找需要遍历，二分查找在链表中的效率可能不如数组等随机访问数据结构，因为链表元素不是连续存储在内存中的。因此，在设计数据结构时，需要根据实际情况选择是否采用链表作为查找的数据结构。

给定两个单向链表(长度分别为M,N),链表的尾部有部分重合(长度为S),找到重合的部分,输出重合的部分,和重合部分在两个链表中的位置。

算法思路：

1. 计算两个链表的长度差diff；

2. 长链表先移动diff个节点，然后和短链表一起向后遍历，直到找到第一个相同的节点；

3. 如果两个链表没有重合部分，则返回null；

4. 如果有重合部分，则返回重合部分的起始节点和两个链表中的位置。

代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 计算两个链表的长度
    lenA, lenB = 0, 0
    pA, pB = headA, headB
    while pA:
        lenA += 1
        pA = pA.next
    while pB:
        lenB += 1
        pB = pB.next

    # 长度差
    diff = abs(lenA - lenB)
    # 长链表先移动diff个节点
    pA, pB = headA, headB
    if lenA > lenB:
        for i in range(diff):
            pA = pA.next
    else:
        for i in range(diff):
            pB = pB.next

    # 一起向后遍历，找到第一个相同的节点
    while pA and pB and pA != pB:
        pA = pA.next
        pB = pB.next

    if pA == pB:
        return pA
    else:
        return None

时间复杂度：$O(m+n)$，其中m和n分别是两个链表的长度。