链表python 循环链表python

Python中的链表实现与应用

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针，在Python中，我们可以使用类来实现链表，以下是一个简单的链表实现及其应用示例。

我们定义一个链表节点类ListNode，用于表示链表中的每个节点：

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None

接下来，我们定义一个链表类LinkedList，用于表示整个链表：

class LinkedList:
    def __init__(self):
        self.head = None
    def is_empty(self):
        return self.head is None
    def get_length(self):
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count
    def append(self, value):
        node = ListNode(value)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
    def add_at_head(self, value):
        node = ListNode(value)
        node.next = self.head
        self.head = node
    def add_at_index(self, index, value):
        if index <= 0:
            self.add_at_head(value)
        elif index > self.get_length() - 1:
            self.append(value)
        else:
            node = ListNode(value)
            cur = self.head
            count = 0
            while count < index - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node
    def delete(self, value):
        cur = self.head
        pre = None
        while cur is not None:
            if cur.value == value:
                if not pre:
                    self.head = cur.next
                else:
                    pre.next = cur.next
                return True
            else:
                pre = cur
                cur = cur.next
        return False
    def search(self, value):
        cur = self.head
        while cur is not None:
            if cur.value == value:
                return True
            cur = cur.next
        return False
    def print_list(self):
        cur = self.head
        while cur is not None:
            print(cur.value, end=' -> ')
            cur = cur.next
        print('None')

现在我们已经实现了链表的基本操作，接下来我们来展示一些链表的应用示例：

1、反转链表：我们可以使用双指针法来实现链表的反转，具体步骤如下：

- 初始化两个指针pre和cur，分别指向链表的头节点和尾节点；

- 当cur不为空时，将cur的下一个节点指向pre，然后将pre和cur向后移动一位；

- 最后返回pre作为新的头节点。

def reverse_linked_list(head):
    pre = None
    cur = head
    while cur is not None:
        next_node = cur.next
        cur.next = pre
        pre = cur
        cur = next_node
    return pre

2、合并两个有序链表：我们可以使用归并排序的思想来合并两个有序链表，具体步骤如下：

- 初始化两个指针l1和l2，分别指向两个有序链表的头节点；

- 初始化一个哑节点dummy，用于辅助合并过程；

- 比较l1和l2当前节点的值，将较小的节点添加到dummy的后面，并将对应的指针向后移动一位；

- 当其中一个链表遍历完后，将另一个链表剩余的部分添加到dummy的后面；

- 最后返回dummy的下一个节点作为合并后的链表头节点。

def merge_two_sorted_lists(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        if l1.value < l2.value:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    if l1:
        cur.next = l1
    else:
        cur.next = l2
    return dummy.next

3、删除链表中重复的元素：我们可以遍历链表，对于每个节点，检查其后面的节点是否与当前节点的值相同，如果相同则删除后面的节点，具体步骤如下：

- 初始化一个指针cur，指向链表的头节点；

- 当cur不为空且cur.next不为空时，比较cur和cur.next的值，如果相同则删除cur.next，并将cur向后移动一位；

- 否则将cur向后移动一位；

- 最后返回处理后的链表头节点。

def remove_duplicates(head):
    cur = head
    while cur and cur.next:
        if cur.value == cur.next.value:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

通过以上示例，我们可以看到链表在Python中的应用非常广泛，在实际开发中，我们可以根据需要选择合适的链表实现方式，以满足不同的需求。