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

乙醇收录于博客合集

2025-06-17 约 351 字预计阅读 2 分钟

链表是常用的数据结构，简单起见，我们这里只讨论单向链表。

定义

在一些静态语言中，我们可以用数组去存储一组数据，然而数组的大小是固定是，当数组存满了之后，再往里存东西就会有数组越界的错误。

链表可以解决这个问题，我们可以动态的添加和删除链表中的元素，而不需要考虑链表的容量。

链表长下面这个样子。

对于链表来说，链表中的每一个节点我们称之为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

原始封面

目录

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

定义

基本操作

使用python实现

问题