已知单链表[tex=0.714x1.0]ravtxd2oof9d0U26ZFAIhw==[/tex](带头节点)是一个递增有序表，试写一高效算法,删除表中值大于[tex=1.857x1.0]Ve9bEhOtZUXzk+oXeNyN0Q==[/tex]且小于[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]的节点(若表中有这样的节点),同时释放被删节点的空间,这里[tex=1.857x1.0]Ve9bEhOtZUXzk+oXeNyN0Q==[/tex]和 [tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/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=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]总是保留两数比较时较大的那个值。具体方法如 下：先将[tex=0.571x0.786]HXNXn3AXpwdIpZt8+6oCEw==[/tex]的值赋给 [tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex], 如果[tex=3.786x1.071]9XcA95wwXcYVq3bbG73jNx9EcvaRf6bi2LyqqV9mvL8=[/tex]则将[tex=0.571x1.0]rXP8qnC1QrKspQeJVD0V8A==[/tex]的值赋给[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex], 然后再用 [tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]与[tex=0.5x0.786]EL0hSqs6jZBGdsmH7TMShQ==[/tex]进行比较, 如果[tex=3.643x0.929]hhh7yrq7GIL2IiIuVIlYiQnjp2EpZqOEUqo4ki3P2sE=[/tex] 则将[tex=0.5x0.786]EL0hSqs6jZBGdsmH7TMShQ==[/tex] 的值赋给[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex], 这样能使[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]总是保留最大的值。 最后输出[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]。)
- 设计一个算法判定单链表[tex=0.714x1.0]ravtxd2oof9d0U26ZFAIhw==[/tex](带头节点)是否是递增的。
- 用带头节点的单链表表示整数集合,完成以下算法并分析时间复杂度:[tex=1.286x1.357]VAHhaW1te0xvoqDVN54/dg==[/tex]设计一个算法求两个集合 [tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex] 和 [tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex]的差运算,即 [tex=3.786x1.143]KO3URhTBfbqNu5waallC4A==[/tex]。要求算法的空间复杂度为[tex=2.071x1.357]4tn8z3a70oWd+Kan/q/D8g==[/tex],并释放单链表[tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex]和[tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex]中不需要的节点。[tex=1.286x1.357]BEB68bP4vOVk/XYYizw11w==[/tex] 假设集合中的元素按递增排列，设计一个高效算江求两个集合 [tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex] 和[tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex]的差运算, 即 [tex=3.786x1.143]KO3URhTBfbqNu5waallC4A==[/tex] 。要求算法的空间复杂度为 [tex=2.357x1.357]4AO+SoeErUSxnKvIp+lB1w==[/tex] 并释放单链表 [tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex] 和 [tex=0.786x1.0]ri6gmnf1+J9dGqG5/1sV6A==[/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]之后,请分析算法的时间复杂度。