编程笔试题(六)单向链表及链表反转
乙醇 创建于 8 months 之前
最后更新: less than a minute 之前
阅读数: 479
链表是常用的数据结构,简单起见,我们这里只讨论单向链表。
定义
在一些静态语言中,我们可以用数组去存储一组数据,然而数组的大小是固定是,当数组存满了之后,再往里存东西就会有数组越界的错误。
链表可以解决这个问题,我们可以动态的添加和删除链表中的元素,而不需要考虑链表的容量。
链表长下面这个样子。
对于链表来说,链表中的每一个节点我们称之为Node,Node包含1个指针,指向下一个Node节点,链表就是按照一定的顺序把Node给组合起来。其中排在第1位的节点我们称之为链表的头,也就是Head。
在链表中查找数据的过程实际上就是从链表的头开始,然后通过Node的下一个节点指针,一节一节的向后查找。
基本操作
增加一个节点
删除节点
使用python实现
class Node():
def __init__(self, elm):
self.data = elm
self.next = None
def get_value(self):
return self.data
class SinglyLinkedList():
def __init__(self):
self.head = None
self.size = 0
# https://www.programiz.com/python-programming/generator
def __iter__(self):
current = self.head
while current:
yield current
current = current.next
raise StopIteration
def __contains__(self, elm):
found = False
current = self.head
while current:
if current.get_value() == elm:
found = True
break
else:
current = current.next
return found
def get_tail(self):
tail = self.head
if tail is None:
return None
while tail.next:
tail = tail.next
return tail
def get_head(self):
return self.head
def is_empty(self):
return self.size == 0
def get_size(self):
return self.size
def append(self, elm):
node = Node(elm)
tail = self.get_tail()
if tail:
tail.next = node
else:
self.head = node
self.size = self.size + 1
return node
def delete(self, elm):
if self.head is None:
return
current = self.head
prev = None
while current:
if current.get_value() == elm:
if prev is not None:
prev.next = current.next
else:
self.head = current.next
self.size = self.size - 1
return
else:
prev = current
current = current.next
import unittest
class SinglyLinkedListTestCase(unittest.TestCase):
def test_append(self):
l = SinglyLinkedList()
self.assertTrue(l.is_empty())
# 1
l.append(1)
self.assertEqual(l.get_size(), 1)
self.assertEqual(l.get_head().get_value(), 1)
self.assertEqual(l.get_tail().get_value(), 1)
# 1 2
l.append(2)
self.assertEqual(l.get_size(), 2)
self.assertEqual(l.get_head().get_value(), 1)
self.assertEqual(l.get_tail().get_value(), 2)
# 1 2 3
l.append(3)
self.assertEqual(l.get_size(), 3)
self.assertEqual(l.get_head().get_value(), 1)
self.assertEqual(l.get_tail().get_value(), 3)
def test_in(self):
l = SinglyLinkedList()
self.assertTrue(l.is_empty())
l.append(1)
l.append(3)
l.append(5)
self.assertTrue(1 in l)
self.assertTrue(3 in l)
self.assertTrue(5 in l)
self.assertFalse(2 in l)
self.assertFalse(4 in l)
self.assertFalse(6 in l)
def test_delete(self):
l = SinglyLinkedList()
self.assertTrue(l.is_empty())
l.append(1)
l.append(3)
l.append(5)
# 1 3 5 -> 3 5
l.delete(1)
self.assertEqual(l.get_head().get_value(), 3)
self.assertEqual(l.get_tail().get_value(), 5)
self.assertEqual(l.get_size(), 2)
l.delete(4)
self.assertEqual(l.get_head().get_value(), 3)
self.assertEqual(l.get_tail().get_value(), 5)
self.assertEqual(l.get_size(), 2)
# 3 5 -> 3
l.delete(5)
self.assertEqual(l.get_head().get_value(), 3)
self.assertEqual(l.get_size(), 1)
# 3 -> None
l.delete(3)
self.assertEqual(l.get_size(), 0)
self.assertTrue(l.get_head() is None)
l.append(4)
l.delete(4)
self.assertEqual(l.get_size(), 0)
self.assertTrue(l.get_head() is None)
if __name__ == "__main__":
unittest.main()
问题
针对上面的单向列表,实现列表的反转。
过程如下
代码实现如下
def reverse(self):
if self.head is None or self.size == 1:
return None
current = self.head
prev = None
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev