链表Linked List常用代码片段

本文介绍了面试中关于Linked List的一些常用代码片段。

关于单链表最基础的知识就不说了,链表中每一个Node都可以用以下的class表示:

1
2
3
4
Class Node:
self.__init__(self, val = -1, next = None):
self.val = val
self.next = next

在上算法课的时候可能还会更加完善的定义一个class单纯表示LinkedList,里面只有一个叫head的Node实例,但是在面试里为了简略没有这种必要。一般假设直接把链表头的Node作为一个input variable。

Traverse a linked list

链表的本质就是在上一个Node里存储下一个Node的地址,以便于我们可以遍历整个链表。

1
2
3
4
5
def traverse_linked_list(head):
curr = head #指针
while curr: #当指针没有指到末尾
# 访问当前Node
curr = curr.next #指针指向下一个Node

如果最后需要复制一份当前的linked list,或者根据当前链表返回一个新的链表(比如说Leetcode#2),为了简便,我们常常先规定一个dummy node作为开头。

1
2
3
4
5
6
7
8
9
10
def return_a_copied_list(head):
#dummy是最后要返回的链表头,curr是旧链表当前的位置,curr_new是返回链表的尾部
curr = head
dummy = Node()
curr_new = dummy
while curr:
curr_new.next = Node(curr.val)
curr_new = curr_new.next
curr = curr.next
return dummy.next #最后返回的时候需要删除最开始的dummy node

你当然可以直接更新head成head.next,但我们就无法再追踪到输入链表的头部了。

Reverse a linked list

很多题目里需要把一个linked list倒过来,这种需求的话因为我们还是只能从头访问链表,如果需要in place变换的话, 只需要一前一后两个指针,后指针是还没有变换过的剩余链表的头,前指针是反链表的尾部,在当前轮次,我们需要将后指针的next指向反链表的尾部,再更新前后指针,举一个例子:

1
2
3
4
5
6
7
8
9
10
11
# 1->2->3->4
# None<-1 2->3->4 (prev:1, curr = 2)
# None<-1<-2 3->4 (prev:2, curr = 3)
# None<-1<-2<-3 4 (prev:3, curr = 4)
# None<-1<-2<-3<-4 (prev:4, curr = None) end
def reverse_in_place(head):
prev, curr = None, head
while curr:
tmp = curr.next #记录curr.next因为马上我们要把curr.next指向prev了
curr.next, prev, curr = prev, curr, tmp
return prev

如果你需要边reverse边构建一个新的linkedlist,那么prev指针永远指向新链表的头,curr只起到一个遍历旧链表的作用,代码可以改成:

1
2
3
4
5
6
7
def reverse(head):
prev, curr = None, head
while curr:
tmp = Node(curr.val)
tmp.next, prev = prev, tmp
curr = curr.next
return prev

Slow and fast pointers

快慢指针指的是两个指针从相同的起点一起开始跑,快指针每次跑两格,慢指针每次跑一格。这样当快指针跑到链表末尾的时候,慢指针正好处于链表的中间点。这种方法常常用来将链表等分为两份。按照需求,也可以有第三个指针slow_prev每次都更新为slow的前面一个Node,然后在最后的时候设置其next为None,这样就可以把链表分为两个子链表。

1
2
3
4
5
6
7
8
def split_linked_list(head):
if not head or not head.next: #链表长度为0或1时
return head
slow, fast, slow_prev = head, head, None
while fast and fast.next:
fast, slow_prev, slow = fast.next.next, slow, slow.next
slow_prev.next = None #这里slow_prev不可能为None,故为安全的访问
return [head, slow] #return two sub linked list

将快慢指针都初始化为head的话,slow指针最后要么指向最中间的元素(奇数个Node情况下),要么指向后部第一个元素(偶数个Node的情况下)。

1
2
3
4
5
# 1,2,3,4,5,6
# slow,fast = 1,1 -> 2,3 -> 3,5 -> 4,None slow = 4
#
# 1,2,3,4,5,6,7
# slow,fast = 1,1 -> 2,3 -> 3,5 -> 4,7 slow = 4