现在算法是大厂面试的必考题，而且越来越难，已经不是简单的列表，字符串操作了，会涉及到各种数据结结构。单链表的反转也是经常考的一道题，里面故在此记录一下。
顺序存储元素，但是元素在空间上是不连续的，所以在链表每个元素中除了存储元素的值，还会存储下一个元素的地址，单链表的话就只有指向下一个元素的指针，双向链表的话还会有指向前一个元素的指针。正是由于链表以上的存储特点，在做插入和删除操作时只需要断开指针的连接，不需要移动后面的数据，所以对链表修改的效率会很高，但是查找的效率会很低，这也正是链表和数组的区别。链表的存储示意图：
完成这道题至少有3种方式：
1.先对原链表做头部删操作，再对新链表做头部插入操作；
2.通过3个指针实现，p0指向前一个节点的指针，p1表示当前节点的指针，p2表示下一个节点的指针
3.用递归实现；
1)创建一个新的空列表；
2）取出旧链表中头结点的元素，将其next指针设置为新链表的头指针，同时将旧链表的头结点执行下一个元素
3）依次重复第2）步的操作，直到取出就链表中所有的节点。
4）最后形成的新链表如下，实现了反转的功能：
5）代码实现：
# encoding=utf-8 import copy class Node: """节点类，包含值和下一个节点的指针""" def __init__(self, value, next=None): self.value = value self.next = next def __str__(self): return "Node value:%s" % self.value class LinkedList: def __init__(self, head=None, tail=None): self.head = head self.tail = tail def get_all(self): """获取链表中所有的节点""" nodes = [] temp = self.head while temp: nodes.append(temp.value) temp = temp.next return nodes def add_node(self, value): """在列表中添加节点""" node = Node(value) # 空链表,收尾指针都指向新增加的节点 if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node def reverse_list(self): """反转单向列表 思路一：先对原链表做头删操作，再对新链表做头插 """ # 定义一个新的链表 new_list_node = LinkedList() temp = copy.deepcopy(self.head) while temp: # 1.对之前的链表做头删除操作 node = temp temp = temp.next # 2.对新的链表做头插入操作 if new_list_node.head is None: new_list_node.tail = node node.next = new_list_node.head new_list_node.head = node return new_list_node if __name__ == "__main__": l = LinkedList() for i in range(5): l.add_node(i) new_list_node = l.reverse_list() print(new_list_node.get_all()) print(new_list_node.tail)
借助3个指针来实现反转，p0之前前一个节点，p1指向当前操作的节点，p2指向下一个节点。操作过程如下：将p1的next指针之前p0，之后将p0指向p1节点，p1指向p2节点，如果p1不为空，重复以上操作，最后，p0即为新列表的头节点。
1）开始时p0为空；将p1指向链表的头节点，p1节点的next指针指向p0；p2指向下一个节点：
2）调整3个指针的指向：将p0指向p1；p1指向p2，p1的next指向p0；p2指向下一个节点
3）循环执行以上步骤，直到p1指向的节点不为空，最后得到的链表为：
4）代码实现：
# encoding=utf-8 import copy class Node: """节点类，包含值和下一个节点的指针""" def __init__(self, value, next=None): self.value = value self.next = next def __str__(self): return "Node value:%s" % self.value class LinkedList: def __init__(self, head=None, tail=None): self.head = head self.tail = tail def get_all(self): """获取链表中所有的节点""" nodes = [] temp = self.head while temp: nodes.append(temp.value) temp = temp.next return nodes def add_node(self, value): """在列表中添加节点""" node = Node(value) # 空链表,收尾指针都指向新增加的节点 if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node def reverse_list(self): """ 反转单向列表 思路二：通过3个指针实现，p0指向前一个节点的指针，p1表示当前节点的指针，p2表示下一个节点的指针 :return: LinkedList 对象 """ p1 = copy.deepcopy(self.head) p2 = p1.next # 定义一个新的链表对象 new_list_node = LinkedList() while p1: if new_list_node.head is None: new_list_node.tail = p1 # 将p1的next指向新链表的头结点 p1.next = new_list_node.head # 将新链表的头结点指向p1 new_list_node.head = p1 # 将p1指向p2 p1 = p2 # 判断p2是否指向了链表的末尾 if p2: p2 = p2.next return new_list_node if __name__ == "__main__": l = LinkedList() for i in range(5): l.add_node(i) new_list_node = l.reverse_list() print(new_list_node.get_all()) print(new_list_node.tail)
递归就是将问题分解为处理过程一致的子问题进行处理，但是一定要要结束条件。链表的反转也可以采用递归的方式实现，每次传入的节点不是最后一个的话，就将下一个节点作为参数传递进去，递归调用；直到传入的是最后一个节点时开始逐级返回。
1）将链表中每个节点作为参数，依次传入到reverse_list函数中；
2）当传入的是最后一个节点时，以此节点为头结点创建一个新的链表，并将此链表返回；
3）上一级的调用者接受到返回的链表后，将传入的节点作为链表的尾结点放到链表中；
4）逐级返回，直到回到最开始执行reverse_list函数中，将生成的新链表返回即可
5）代码实现：
# encoding=utf-8 import copy class Node: """节点类，包含值和下一个节点的指针""" def __init__(self, value, next=None): self.value = value self.next = next def __str__(self): return "Node value:%s" % self.value class LinkedList: def __init__(self, head=None, tail=None): self.head = head self.tail = tail def get_all(self): """获取链表中所有的节点""" nodes = [] temp = self.head while temp: nodes.append(temp.value) temp = temp.next return nodes def add_node(self, value): """在列表中添加节点""" node = Node(value) # 空链表,收尾指针都指向新增加的节点 if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node def reverse_list(self, node): """ 反转单链表 思路三：用递归实现 :return:LinkedList 对象 """ if node.next is None: return LinkedList(node, node) temp = copy.deepcopy(node) # 断开当前节点的连接 temp.next = None # 将当前节点放到内层递归返回的链表结尾 l = self.reverse_list(node.next) l.tail.next = temp l.tail = temp return l if __name__ == "__main__": l = LinkedList() for i in range(5): l.add_node(i) new_list_node = l.reverse_list1() print(new_list_node.get_all()) print(new_list_node.tail)
