Python数据结构之链表详解( 四 ) _链表

以上代码输出如下：

在位置1添加grape后链表数据： [pear-->grape-->apple-->orange-->lemon] 修改链表数据后： [pear-->grape-->orange-->lemon] 删除pear后链表数据： [grape-->orange-->lemon] 添加watermelon后链表数据： [grape-->orange-->lemon-->watermelon]

3.2 利用单链表基本操作实现复杂操作[1] 利用基本运算函数，将一单链表逆置，如下图 (a) 所示为逆置前链表，图 (b) 为逆置后链表，并要求算法的空间复杂度为O(1)：

文章插图

为了保证算法的空间复杂度为O(1)，只能修改原结点的指针，设置指针 current，令其指向 head->next，并令head.next=None，然后使用 current 指针依次遍历每个结点并插入到 head 之后。该算法只需要对链表顺序扫描一遍即可完成倒置，因此时间复杂度为O(n)，算法实现如下：

def reverse_linked_list(sllist):head_node = sllist.headif head_node.next:current = head_node.nexthead_node.next = Nonesllist.length = 0while current:previous = currentcurrent = current.nextsllist.insert_node(0, previous)return sllist# 算法测试sllist = SinglyLinkedList()for i in range(5):sllist.append(i)print('逆置前：', sllist)print('逆置后：', reverse_linked_list(sllist))

算法输出如下：

逆置前： [0-->1-->2-->3-->4] 逆置后： [4-->3-->2-->1-->0]

算法执行流程如下所示：

文章插图

[2] 删除单链表中的重复结点，如下图操作所示，(a) 为删除前的情况，(b) 为删除后的状态。

文章插图

用指针 previous 指向第一个数据结点，并使用另一个指针 curent 指向 previous 的直接后继开始遍历整个链表，当遇到具有相同的数据元素的结点时将其删除；然后 previous 指向下一个结点，重复删除过程；直到 previous 指向最后结点时算法结束：

def delete_same_node(sllist):previous = sllist.head.nextif not previous:returnwhile previous:current = previouswhile current.next:if current.next.data == previous.data:same = current.nextcurrent.next = current.next.nextsllist.length -= 1del sameelse:current = current.nextprevious = previous.nextreturn sllist# 算法测试sllist = SinglyLinkedList()print('删除重复结点前：', sllist)sllist.append(10)sllist.append(11)sllist.append(10)sllist.append(10)sllist.append(11)print('删除重复结点后', delete_same_node(sllist))

该算法的时间复杂度为O(n2)，程序输出如下：