已知指针[tex=1.143x1.0]zKKWhru0rnVESFIFZKOLFA==[/tex]和[tex=1.071x1.0]ZgYY6BtTUaSv3WmvlB/UFg==[/tex]分别指向两个单链表的头结点，并且已知两个链表的长度分别为[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]和[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]。试写一算法将这两个链表连接在一起，假设指针[tex=1.071x1.0]ZS5PIlX5c2Bd02F/FFD3Jw==[/tex]指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
举一反三
- 已知[tex=1.5x1.0]P0hU/5NocOVtvi3hWl+UXg==[/tex]和[tex=1.214x1.0]jHH+9poy2Bp0CUbqOwtn7w==[/tex]分别指向两个单链表的头节点,且已知其长度分别为[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]和[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]。试写一算法将[tex=1.214x1.0]jHH+9poy2Bp0CUbqOwtn7w==[/tex]连接到[tex=1.214x1.0]YTQ9kROO7Cn7aiKy4nOP2w==[/tex]之后,请分析算法的时间复杂度。
- 设非空线性表[tex=1.143x1.0]73Q9EHmRwi9uo+/JGLkIow==[/tex]和[tex=1.071x1.0]EpxkuOteKSV9yVeQUNWkQw==[/tex] 都用带头节点的循环双链表表示。设计一个算法[tex=6.929x1.357]me08v1IR/a8OTY+4pfJquA6MIR5dCgOjW8BOKL0sFXk=[/tex] 。其功能是 [tex=1.643x1.0]GhjBbQADxSn49uq2Aym9oA==[/tex]时,将线性表 [tex=1.071x1.0]EpxkuOteKSV9yVeQUNWkQw==[/tex] 插入到线性表 [tex=1.143x1.0]73Q9EHmRwi9uo+/JGLkIow==[/tex] 的最前面; 当[tex=2.214x1.071]OdErvKDfCZ2D49AN5H7nvA==[/tex] 时,将线 性表 [tex=1.071x1.0]ZgYY6BtTUaSv3WmvlB/UFg==[/tex] 插入到线性表 [tex=1.143x1.0]73Q9EHmRwi9uo+/JGLkIow==[/tex]中第[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex] 个节点的后面;当[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex] 大于等于线性表 [tex=1.143x1.0]73Q9EHmRwi9uo+/JGLkIow==[/tex] 的长度吋,将线性表 [tex=1.071x1.0]ZgYY6BtTUaSv3WmvlB/UFg==[/tex]插入到线性表 [tex=1.143x1.0]zKKWhru0rnVESFIFZKOLFA==[/tex] 的最后面。
- 编写一个函数，将一个头结点指针为[tex=0.571x0.786]HXNXn3AXpwdIpZt8+6oCEw==[/tex]的单链表[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex]分解成两个单链表[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex] 和 [tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex], 其头结点指针分别为[tex=0.571x0.786]HXNXn3AXpwdIpZt8+6oCEw==[/tex]和[tex=0.429x1.0]Q2fWySASH/4Xf2eu85OwAQ==[/tex], 使得[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex]链表中含有原链表[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex]中序号为奇数 (第 1,3, [tex=1.286x0.786]lRSLJav0cvc1uYdx/9plcw==[/tex]) 的元素 (头结点紧接的下一个元素为第 1 个元素 )，而[tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex]链表中含有原链表[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex]中序号为偶数 第 2，4，[tex=1.286x0.786]lRSLJav0cvc1uYdx/9plcw==[/tex]) 的元素，且保持原来的相对顺序。
- 设[tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex]和[tex=0.786x1.0]ri6gmnf1+J9dGqG5/1sV6A==[/tex]是两个单链表(带头节点),其表中元素递增有序。试写一算法将[tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex]和[tex=0.786x1.0]ri6gmnf1+J9dGqG5/1sV6A==[/tex]归并成一个按元素值递增有序的单链表[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex],并要求辅助空间为[tex=2.071x1.357]4tn8z3a70oWd+Kan/q/D8g==[/tex],请分析算法的时间复杂度。
- 假设在长度大于[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]的循环单链表中,既无头节点指针也无首数据节点指针。[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]为指向链表中某个节点的指针,试编写算法删除节点[tex=1.0x0.786]yaoihnBqKeopk1SSk/C8rw==[/tex]的前驱节点。