编程笔试题(六)单向链表及链表反转

乙醇 创建于 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

0

相关课程

mockito简明教程
图文
mockito简明教程

课程分类: 测试工具

mock工具

  • 已完结
  • 已更新7集
  • 最后更新时间: 2024-03-18 12:50:29

免费

查看详情
requests从入门到精通
图文
requests从入门到精通

课程分类: 测试工具 接口测试

python接口测试必会

  • 已完结
  • 已更新16集
  • 最后更新时间: 2024-03-18 12:54:40

免费

查看详情
Locust实用教程
图文
Locust实用教程

课程分类: 性能测试 测试工具

python语言实现的非常出色性能测试工具

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-18 12:24:59

免费

查看详情
TDD测试驱动开发教程
图文
TDD测试驱动开发教程

课程分类: 测试框架 软件测试基础

TDD其实并不神秘

  • 已完结
  • 已更新7集
  • 最后更新时间: 2024-03-18 11:53:22

免费

查看详情
软件测试基础教程
图文
软件测试基础教程

课程分类: 软件测试基础

转码和转行必备

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-18 11:40:05

免费

查看详情
软件测试入门教程
图文
软件测试入门教程

课程分类: 软件测试基础

新人如何转码到软件测试

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-17 11:07:23

免费

查看详情