|
今天刷到了一个复制链表的题目?，具体要求是给定一个单链表，你需要对这个链表进行复制并且返回这个新链表的头节点。
这个的思路我们可以想象成我们用双指针，去遍历给定的链表，然后pre指针用来不断的往后移动，去创建最新的链表，dum指针用来保存最初的头节点，最后因为我们在最开始创建了一个Node(0), 所以我们到最后返回的是dum.next而不是dum，这一点需要注意。
# 这里是单链表的定义
class Node(object):
def __init__(self, item):
self.val = item
self.next = None
def copyList(head):
cur = head # 当前节点
pre = Node(0) # 复制新链表的起点
dum = pre # 我们用dum来保存新链表的首个节点
while cur:
node = Node(cur.val) # 复制链表的第一个节点
pre.next = node # 让新链表的起点指向 第一个节点
cur = cur.next # 旧链表下一个节点
pre = node # 新链表下一个节点
return dum.next # 返回新链表的起点， 不用pre因为pre已经到了链表的最后
if __name__ == "__main__":
# 这里我们创建一个链表
a = Node(5)
b = Node(4)
c = Node(3)
a.next = b
b.next = c
new_list = copyList(a)
while new_list:
print(new_list.val)
new_list = new_list.next
?
|