题目:复制一个线性链表
解题思路:已知一个线性链表,要产生一个与已知线性链表完全等价的另外一个线性链表。这里假设已知线性链表lista指出,经复制以后产生的线性链表有listb指出。
下面将该操作设计为一个递归算法。其操作可以描述为以下:
1.若lista为空,则返回空指针。
2.若lista非空,则复制lista所指的链结点,并将该链结点的指针赋予listb;然后复制该链结点的直接后继结点,并将该直接后继结点的指针赋予listb->link,最后返回新复制的线性链结点的第1个链结点指针listb。
具体算法实现如下:
这里我们会用到toString(list))来打印一个线性链表出来。
这里我们会用到createLinklist(n)来建立一个线性链表出来
function copy(list) {
let listb
if ( list == null) {
return null
} else {
listb = new Node()
listb.data = list.data
listb.link = arguments.callee(list.link)
}
return listb
}
var lista = createLinklist(5)
console.log('创建的list为:', toString(lista))
var r_list = copy(lista)
console.log('复制后的链表为:', toString(r_list))
console.log( r_list==lista )