前言：
而今兄弟们对“python实现循环链表”大致比较关心，小伙伴们都想要知道一些“python实现循环链表”的相关文章。那么小编在网上收集了一些对于“python实现循环链表””的相关知识，希望我们能喜欢，咱们快快来学习一下吧！链表(维基百科)
简单讲一下链表linked list是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。单向链表（又名单链表、线性链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取.
2964628074
定义
我们来看一下单向链表的定义实现：
1
2
3
4
class ListNode(object):
def __init__(self, value):
self.value = value
self.next = None
一个节点有value的属性定义该节点的值，还有一个next的指针，指向下一个节点，类似于1>2>4>5>6>3这样。
操作
单向链表的操作主要有：添加一个节点，删除一个节点，遍历一条链表，具体的实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def add(pre, new_node):
"""
pre节点后面插入一个新的节点
:param pre: pre节点
:param new_node: 新插入的节点
:return:
"""
new_code.next = pre.next
pre.next = new_node
def delete(pre):
"""
pre节点的后面删除一个节点
:return:
"""
if pre.next:
pre.next = pre.next.next
def traverse(head):
while head:
print(head.value)
head = head.next
在pre节点后面插入一个节点：只需要把新节点的指针指向pre节点指针指向的节点，把pre节点的指针指向新节点。
在pre节点后面删除一个节点：只需要把pre节点的指针指向pre节点的指针的指针节点(要注意pre节点的指针不为None)
题目
我们来看一个关于链表的一个算法题，来自于leetcode:
删除链表中的元素
删除链表中等于给定值 val 的所有元素。
示例
给定: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
返回: 1 --> 2 --> 3 --> 4 --> 5
分析：一般来讲，我们首先会考虑到遍历一下这个链表，移除掉value值等于给定val的节点就好。但是这里要返回一个新的链表，我们知道，对于单向链表，我们只能知道当前元素的后置节点，而不知道当前元素的前置节点。所以我们要构建一个前置节点。
看代码：
def removeElements(head, val):
"""
:param head: listNode
:param val: int
:return: listNode
"""
dump = ListNode(-1)
dump.next = head
cur = head
pre = dump
while cur:
if cur.value == val:
pre.next = cur.next
else:
pre = pre.next
cur = cur.next
return dump.next
我们构建一个dump节点作为第一个节点，cur节点为当前循环的节点，pre节点为cur节点的前置节点。
当前节点的value为给定val的时候，把当前cur的前置节点pre指针指向cur的后置节点，也就是cur.next。然后接着遍历这个链表。
由于第一个节点dump是我们自己构造的(我用的值是-1，你可以用其他不为val的值，一般使用-1)，它的next是给出的head，我们只是对head做了调整。所以最后新的列表就是dump.next,也就是调整后的head。
给定两个非空链表来代表两个非负整数，位数按照逆序方式存储，它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
分析：
因为是位数按照逆序方式存储，所以链表的前置节点是地位，直接循环链表相加，生成新的链表即可。这里要注意，链表1和链表2长度不一样的情况。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def addTwoNumbers(l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
pre_node = ListNode(0)
cur = pre_node
n = 0
while l1 or l2:
n1 = n2 = 0
if l1:
n1 = l1.val
l1 = l1.next
if l2:
n2 = l2.val
l2 = l2.next
sumnum = n1 + n2 + n
n = sumnum / 10
cur.next = ListNode(sumnum % 10)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if n > 0:
cur.next = ListNode(n)
return pre_node.next
进阶版的两数相加，来自于leetcode:
两数相加II
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)输出: 7 -> 8 -> 0 -> 7
分析：
因为数字最高位位于链表的开始，而加减法我们不倾向于从高位做加减，但是又不允许对列表做翻转，那我们想到一个数据结构，栈。栈是先进后出，可以把列表压进一个栈中，再循环出栈的时间先出的就是低位，后出的就是高位，我们再按照上一个demo的方法做加减就好了。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Stack:
"""模拟栈"""
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
s1 = Stack()
s2 = Stack()
n = 0
cur_node = ListNode(-1)
while l1:
s1.push(l1.val)
l1 = l1.next
while l2:
s2.push(l2.val)
l2 = l2.next
while (not s1.isEmpty()) or (not s2.isEmpty()) or n:
num1 = s1.pop() if not s1.isEmpty() else 0
num2 = s2.pop() if not s2.isEmpty() else 0
sumnum = num1 + num2 + n
n = sumnum / 10
cur_node.val = sumnum % 10
pre_node = ListNode(-1)
pre_node.next = cur_node
cur_node = pre_node
return cur_node.next
标签： #python实现循环链表
