入门单链表
链表简介
链表（linked list）作为一种常见的数据结构，通常由数据和指针组合而成。在一些没有指针结构的程序语言中，如 python、java等,指针被引用所代替。链表中的每个节点通过指针或引用相连接，你可以通过指针或者引用来遍历节点。
下图为单个节点的构成：
链表也有很多种形式，有单链表、循环链表、双向链表，下面我们介绍一种常用的单链表：
在单链表中，每个节点包括指向下一个节点的指针。但是单链表的首尾节点却特立独行，头结点只有指针，却没有数据；尾节点恰好相反，只有数据，没有指针，也就是提示我们链表后面不再有其他的节点。当我们找到第一个节点的时候，我们可以很轻松的获取链表其余节点。
这就像小时候玩游戏，一群小伙伴排成一排，手拉着手。左手被别人握紧，右手也紧紧握住别人的左手。左手就代表数据，右手代表指针。从第一个同学开始，这种通过左右手建立的联系，使我们很轻松的就找到了每一个人的位置。如果有一个小伙伴要加入，他会被分配在自己最好的朋友的前面，姑且将其记作“友人A”，我们就从第一个小伙伴开始遍历，如果找到了一个右手握住“友人A”的同学，姑且记作“同学B”，我们就停下来。先让这个小伙伴紧紧抓住“友人A”的右手，再让“同学B”握住他的左手。这样，这位小伙伴就找了自己的归宿。如果走遍了这条长长的队伍，还有没有找到属于自己的联系，那就稍稍有些寂寞了。如果有的人最好的”朋友C”变心了，他要出局了。我们还是要从第一个人开始遍历这条长长的队伍，一旦我们找到这个人前面的“同学D”，让“同学D”握住”朋友C“的手，然后再断开这个人与”朋友C“之间的羁绊，这个人重又恢复了自由身，尽管有少许的寂寞。
下面我们用 python 实现简单的单链表：
创建一个节点
建立一个节点很简单，我们只要给节点对象的数据和指针属性赋值即可。头结点和尾节点稍稍有些不同，头结点数据为 None，尾节点指针为 None。
拿上面的例子说，就是没有人握住第一个小朋友的左手，所以说他的数据为空；最后一个小朋友也无法握住别人的左手，所以说他的指向为空。而其他小朋友，左手被别人紧紧握住，右手则紧紧握住别人，即数据与指向都不为空。
class Node(object):
def __init__(self, data, pointer):
self.data = data
self.next = pointer
# 构建了只有首尾结点的链表
node = Node(12,None)
head = Node(None,node)创建单链表
创建链表，就是在链表的尾部增加一个新的尾节点。首先要创建一个新的尾节点，代码为node = Node(value,None)。其次将前面的节点tail指向新创建的尾节点，即 tail的next属性要指向新创建的节点，代码为 tail.next = node。
形象点说，要想在那条队伍后面再加上一个小朋友，只要让末尾的握住新来的左手，那么这条队伍就增加了一名成员。
class SingleLinkedList(object):
def __init__(self):
self.head = Node(None, None)
self.point = self.head
def append(self, data):
# 末尾追加节点
new_node = Node(data, None)
self.point.next = new_node
self.point = new_node插入节点
在特定节点前面插入数据：新建一个节点，然后找到特定节点的前驱结点，然后让新节点的next指向特定节点，而前驱结点也要指向新节点。
但是有些新来的人不甘心站在队伍的末尾，因为末尾的人没有”珍贵之物“（右手没有紧紧握住的对象），他想在队伍中找到命中之人。他就从头一个一个的寻找，直到发现有一个人握住了他的意中人。他就握住意中人的左手，再让前一个人握住他的左手。
def insert(self, data, find):
# 插入数据(前向插入数据)
if not self.head.next:
print('链表为空')
return None
new_node = Node(data, None)
self.point = self.head
while self.point.next.data != find:
self.point = self.point.next
if self.point.next is None:
print('没有找到该元素')
return None
new_node.next = self.point.next
self.point.next = new_node头后插节点
head 节点之后插入节点，如果 head 后没有节点，那么就直接让 head 节点指向新建节点；否则的话，就让新节点指向 head 后一个节点，而 head 再指向新节点。
形象点说，如果第一个人就孤零零的站着，就直接握住新朋友的手就好了。如果第一个人已经有朋友了，就让新朋友握住他的旧朋友的手，他再顺势握住新朋友的手。
def insert_after_head(self, data):
node = Node(data, None)
if not self.head.next:
self.head.next = node
return None
node.next = self.head.next
self.head.next = node删除节点
我们从单链表头部开始遍历，先找到要删除节点的前置节点 p，再新建一个节点 q 指向要删除节点，接着将 p 节点指向要删除节点的下一个节点，最后将 q 节点删除。
形象地说，在队伍中找到这个被”抛弃”之人，让他前面的人撇开他，接着握住他后面的人的左手。然后这个稍微有些可怜的人就被系统判定“出局了”。
def delete(self, find):
# 删除节点
# 判断是否为空链表
if not self.head.next:
print('链表为空')
return None
self.point = self.head
while self.point.next.data != find:
self.point = self.point.next
pointer = self.point.next
self.point.next = self.point.next.next
del pointer数据排序
这个长长的队伍要开始按照身高次序排序了，高个子在后，矮个子在前，即升序的顺序。从第一个人开始，依次问右手边的人，“我比你高吗？”，如果是的话，两个人就交换位置，这一轮下来，最高的人站在了队伍的最后。也就是说，至少有一个人的位置已经确定。紧接着，我们再开始同样的游戏，但这次我们只需要到倒数第二个人就好了，因为已经确定一个人的顺序了。当然如果有一轮下来，我们发现没有人交换位置，说明大家已经按照高矮排好了顺序，就可以结束游戏了。
def sort(self):
# get_size()改变了 self.point 的指向
length = self.get_size()
i, j = 0, 0
flag = 1
while i < length:
self.point = self.head.next
while j < length - i - 1:
if self.point.data > self.point.next.data:
temp = self.point.data
self.point.data = self.point.next.data
self.point.next.data = temp
self.point = self.point.next
j += 1
flag = 0
if flag:
break
i += 1
j = 0求中间节点 只允许遍历一次
如果可以多次遍历的话，我们大可以求出链表的大小，再算出中间节点。但只让遍历一次的话，我们就要用到快慢指针的方法了。形象地说，就是有两个同学在操场上跑步，记为A,B。A 同学跑步速度是 B 同学的二倍，也就是说，A 同学跑完一圈的时候，B 同学刚好跑完半圈。同理，我们用快慢指针来遍历链表，快指针到达尾节点时，慢指针正好指向了中间节点。 代码中体现为，快指针每次前进两个节点，而慢指针只前进一个节点。当快指针指向尾节点时，停止遍历。
# 求中间节点 只允许遍历一次
def quick_middle(self):
slow_point = self.head
fast_point = self.head
while fast_point.next.next:
slow_point = slow_point.next
fast_point = fast_point.next.next
if not fast_point.next:
break
if fast_point.next:
slow_point = slow_point.next
return slow_point.data逆置
新建一个链表，遍历旧链表中的元素。将旧链表中的每一个元素插入到新链表头结点的后面。这样，先插入的数据反而被后插入的数据挤到了后面，原先最前面的数据节点变成了新链表尾节点，而原先的尾节点却变成了新链表最前面的数据节点。风水轮流转，这样就完成了链表的逆置操作。
def reverse(self):
local_list = SingleLinkedList()
self.point = self.head
count = 0
while self.point.next:
count += 1
self.point = self.point.next
data = self.point.data
local_list.insert_after_head(data)打印节点
遍历节点，打印数据。
def print(self):
# 打印结点
self.point = self.head
while self.point.next:
self.point = self.point.next
print('{} ->'.format(self.point.data), end=' ')
print('')删除尾节点
根据链表大小，找到尾节点，然后类似删除节点的操作。
def delete_by_tail(self, num):
size = self.get_size()
assert (num <= size)
assert (num > 0)
pos = size - num
count = 0
self.point = self.head
while count < size:
count += 1
self.point = self.point.next
if count == pos:
pointer = self.point.next
self.point.next = self.point.next.next
del pointer我犯的错误
head 的 next 就指向 node 节点，再让 node 节点指向 head.next，就相当于 node 节点指向了自身，所以循环打印时，永远跳不出循环。
# 典型错法：
# 自身指向自身 打印值时出不去
node = Node(4,None)
head = Node(4,node)
node.next = head.next
i = 0
while node.next:
i += 1
print(node.data)
if i > 12:
break这就是本节的全部内容了，看完了要多多用编程巩固一下哦。