Python数据结构

Question

1、完成链表的倒序
(1)重新创建线性表文件名Ex1_1.py
文件名Ex1_2py(2)在原线性表上操作，不允许创建新表2、完成顺序表中元素的倒序 文件名Ex2.py3、完成两个链表的合并
(1)链表B接到链表A的后面文件名Ex3_1.py
(2)链表B的第一个元素插到链表A的第一个元素的后面，以此类推 文件名Ex3_2.py4、删除链表中多余的元素文件名Ex4.py
5、删除顺序表中多余的元素 文件名Ex5.py

Answer 1

参考GPT和自己的思路：对于这些问题，我给出以下回答：

1、完成链表的倒序
实现链表倒序可以通过递归的方式，从链表的尾部往头部遍历，然后将每个节点的next指针指向前一个节点，最后将头节点的next指针设为None。代码如下：

def reverse_linked_list(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_linked_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

2、完成顺序表中元素的倒序
实现顺序表的倒序可以使用Python的切片操作[::-1]，即将列表从头到尾倒序排列。代码如下：

def reverse_array(arr):
    return arr[::-1]

3、完成两个链表的合并
将链表B接到链表A的后面，可以先找到链表A的最后一个节点，然后将它的next指针指向链表B的头节点。代码如下：

def merge_linked_lists(a, b):
    if a is None:
        return b
    if b is None:
        return a
    tail = a
    while tail.next:
        tail = tail.next
    tail.next = b
    return a

将链表B的第一个元素插到链表A的第一个元素的后面，可以先将链表B的第一个元素的next指针指向链表A的头节点的next指针所指向的节点，然后将链表A的头节点的next指针指向链表B的第一个节点。代码如下：

def merge_linked_lists(a, b):
    if a is None:
        return b
    if b is None:
        return a
    b.next = a.next
    a.next = b
    return a

4、删除链表中多余的元素
删除链表中多余的元素可以使用哈希表存储出现过的元素，然后遍历链表，遇到重复元素就将它从链表中删除。代码如下：

def remove_duplicates(head):
    if head is None:
        return None
    seen = set()
    seen.add(head.val)
    curr = head
    while curr.next:
        if curr.next.val in seen:
            curr.next = curr.next.next
        else:
            seen.add(curr.next.val)
            curr = curr.next
    return head

5、删除顺序表中多余的元素
删除顺序表中多余的元素可以使用Python的set()函数去除重复元素。代码如下：

def remove_duplicates(arr):
    return list(set(arr))