长度为n的链表进行逆序操作，请问他的时间复杂度是多少，并说明理由。2013年计算机考研真题第一题：已知长度为m和n的升序链表，合并成一个长度为m+n的降序链表，它在最坏的情况下的时

Question

长度为n的链表进行逆序操作，请问他的时间复杂度是多少，并说明理由。
2013年计算机考研真题第一题：已知长度为m和n的升序链表，合并成一个长度为m+n的降序链表，它在最坏的情况下的时间复杂度是（）。
A。O(n) B。O(mxn) C。O(min(m,n)) D。O(max(m,n))

Answer 1

这个过程无非就是每次比较这两个升序链表的当前第一个结点，谁小，谁就先被摘下，实施头插入法插入到新链表的表头就可以了，因为无论如何次序，这m + n个结点一定都会执行这个步骤，所以总时间复杂度一定是O(m + n)，自然最合适的答案就是D了