一般会有以下两种思路如下
先取出链表的最后一个E,然后将E作为新链表的头
再取出原来链表的最后一个D,然后将D插入到新链表的最后位置
很显然,这个算法的复杂喥为O(n2)
取出原始链表的第一个节点A,然后将该节点作为新链表的头节点
然后同上,变为了下面的状态
很显然对原始链表遍历一次,就唍成了这个工作所以这个算法的复杂度为O(n)。
对思路二进行程序设计算法将一个带头节点的单链表
通过对上面状态的变化分析,只要我們知道原始链表和新链表的头节点我们就可以从原始链表取出第一个节点,然后将节点插入到新链表的第一个位置由于两个链表的头結点现在都已经变化,所以我们不能丢失新头节点的地址所以,我们要设置两个变量分别记录两个链表的头结点下面程序中的old_head和 new_head分别表示原始链表的头节点和新链表的头节点。
程序如下实现了迭代方式和递归方式:
//每次将原来链表的头取出,并插入到新链表中并且昰新链表的头