# 《数据结构与算法：Python语言描述》一3.4链表的变形和操作

### 3.4.1单链表的简单变形

class LList1(LList):
...... # 方法定义和其他


def __init__(self):
LList.__init__(self)
self._rear = None


def prepend(self, elem):
if self._rear is None:  # 是空表


def prepend(self, elem):
else:


def append(self, elem):
if self._head is None:  # 是空表
else:
self._rear.next = LNode(elem)
self._rear = self._rear.next


def pop_last(self):
if self._head is None:          # 是空表
if p.next is None:              # 表中只有一个元素
e = p.elem
return e
while p.next.next is not None:      # 直到p.next是最后结点
p = p.next
e = p.next.elem
p.next = None
self._rear = p
return e


mlist1 = LList1()
mlist1.prepend(99)
for i in range(11, 20):
mlist1.append(randint(1,20))

for x in mlist1.filter(lambda y: y % 2 == 0):
print(x)


### 3.4.2循环单链表

class LCList:  # 循环单链表类
def __init__(self):
self._rear = None

def is_empty(self):
return self._rear is None

def prepend(self, elem):  # 前端插入
p = LNode(elem)
if self._rear is None:
p.next = p  # 建立一个结点的环
self._rear = p
else:
p.next = self._rear.next
self._rear.next = p

def append(self, elem):  # 尾端插入
self.prepend(elem)
self._rear = self._rear.next

def pop(self): # 前端弹出
if self._rear is None:
p = self._rear.next
if self._rear is p:
self._rear = None
else:
self._rear.next = p.next
return p.elem

def printall(self): 输出表元素
if self.is_empty():
return
p = self._rear.next
while True:
print(p.elem)
if p is self._rear:
break
p = p.next


### 3.4.3双链表

p.prev.next = p.next
p.next.prev = p.prev


class DLNode(LNode):  # 双链表结点类
def __init__(self, elem, prev=None, next_=None):
LNode.__init__(self, elem, next_)
self.prev = prev


class DLList(LList1):              # 双链表类
def __init__(self):
LList1.__init__(self)

def prepend(self, elem):
if self._head is None:     # 空表
self._rear = p
else:                      # 非空表, 设置prev引用
p.next.prev = p

def append(self, elem):
p = DLNode(elem, self._rear, None)
if self._head is None:     # 空表插入
else:                      # 非空表, 设置next引用
p.prev.next = p
self._rear = p

def pop(self):
return e

def pop_last(self):
e = self._rear.elem
self._rear = self._rear.prev
if self._rear is None:
else:
self._rear.next = None
return e


### 3.4.4两个链表操作

def rev(self):
p = None
q._next = p
p = q               # 将刚摘下的结点加入 p 引用的结点序列


Python的list类型有一个sort方法，可以完成list的元素排序。如果lst的值是一个list类型的对象，lst.sort()将把lst中元素从小到大进行排序。另外，也可以用标准函数sorted对各种序列进行排序，sorted(lst)生成一个新的表（list类型的对象），其中元素是lst的元素排序的结果。

1）在操作过程中维护一个排好序的序列片段。初始时该段只包含一个元素，可以是任何一个元素，因为一个元素的序列总应该认为是排序的。
2）每次从尚未处理的元素中取出一个元素，将其插入已排序片段中的正确位置，保持插入后的序列片段仍然是正确排序的。
3）当所有元素都加入了排序的片段时，排序工作完成。

def list_sort(lst):
for i in range(1, len(lst)): # 开始时片段[0:1]已排序
x = lst[i]
j = i
while j > 0 and lst[j-1] > x:
lst[j] = lst[j-1]  # 反序逐个后移元素至确定插入位置
j -= 1
lst[j] = x


def sort1(self):
return
while crt is not None:
x = crt.elem
while p is not crt and p.elem <= x: # 跳过小元素
p = p.next
while p is not crt:                 # 倒换大元素，完成元素插入的工作
y = p.elem
p.elem = x
x = y
p = p.next
crt.elem = x                  # 回填最后一个元素
crt = crt.next


def sort(self):
if p is None or p.next is None:
return

rem = p.next
p.next = None
while rem is not None:
q = None
while p is not None and p.elem <= rem.elem:
q = p
p = p.next
if q is None:
else:
q.next = rem
q = rem
rem = rem.next
q.next = p


### 3.4.5不同链表的简单总结

3.3节和本节介绍了多种不同的链表结构，现在对它们做一个简单的总结，其中讨论时间复杂度时用的n均指表的长度。

|
5天前
|
Python
【Leetcode刷题Python】21. 合并两个有序链表

14 2
|
5天前
|

【Leetcode刷题Python】328. 奇偶链表

12 0
|
5天前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表

13 0
|
4天前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现，通过先序遍历二叉树并调整节点的左右指针，将二叉树转换为先序遍历顺序的单链表。
13 3
|
2天前
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
10 4
|
4天前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
21 5
|
4天前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案，通过使用双指针法找到并删除链表中值为特定数值的节点，然后返回更新后的链表头节点。
13 4
|
5天前
|

【Leetcode刷题Python】23. 合并K个升序链表

6 1
|
5天前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案，包括两种方法：一种是在每个节点后复制一个新节点然后再分离出来形成新链表；另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系，从而处理新链表的构建。
5 1
|
5天前
|

【Leetcode刷题Python】106.相交链表

10 1