python算法-002单链表逆序递归法

作者: DKider | 来源:发表于2019-02-28 21:26 被阅读80次

python算法-002单链表逆序递归法
LeetCode 2. Add Two Numbers
Leetcode-Medium-2 Add Two Number
python算法-003单链表逆序插入法
逆序单链表
单链表逆序
2.单链表
算法学习-单链表反转
leetcode 单链表的各种算法
双向链表

上一篇文章也讲的单链表的逆序，但我没有详细的将过程写出来。这让读者不能够更加快速的理解我写的代码的原理，是我的疏忽，以后会慢慢改进。今天看的一篇文章中说，“如果我能写出清晰的注释和技术规格说明书，其他程序员能够理解我的代码，因此他们就能在自己的代码中使用，而不用重写。如果我做不到这一点，那我的代码对其他人就没有价值。”看到这话，我心里一颤，上一篇文章简直就是一坨shi。

好了，废话不多说，进入正题。

题目：给定一个带头节点的单链表：head->1->2->3->4->5->6->7->8；使其成为：head->8->7->6->5->4->3->2->1。

这次题目与上次一样是将单链表逆序。链表是一种在学习、编写程序等时用的非常多的数据结构。我们这里研究的链表是单链表，而单链表又有带头节点和不带头节点两种。

这里给出带头节点的链表的建立方法：由N个节点链在一起的叫链表，当节点只包含自身存储的数据以及其后继节点的信息的链表叫单链表。python中没有指针的概念，但是引用的功能类似于指针，所以用引用来建立节点之间的关系，为了方便理解，之后的文章可能会用指针来描述。
节点的数据域用data表示，其后继节点域用next表示：

#先建立节点对象LNode
class LNode:
    def __init__(self,arg):
        # 这是数据域data
        self.data = arg    
        # 这是节点的next域，也就是下一个节点的引用
        self.next = None  
"""
方法功能：创建一个带头节点的单链表
"""
def creatLink(x):
    #  x是链表的长度 
    i = 1
    head = LNode(None) # 先构造单链表的头节点
    tmp = None # 用来指向新添加的节点
    cur = head # 用来指向链表的最后一个节点
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head

这次我们使用递归法来实现： 递归程序有两个要素：一是递归定义，一是递归终止条件。我们先来分析一下，如果要将单链表1->2->3->4->5->6->7->8 变成8->7->6->5->4->3->2->1，只需要先把链表变成1->8->7->6->5->4->3->2，然后在将第一个节点1链接到链表的尾部就行了。但是要实现1->8->7->6->5->4->3->2，就需要先把将节点1后面的子链表逆序。同理，要将2->3->4->5->6->7->8逆序，就需要先把链表变成2->8->7->6->5->4->3，然后将节点2链接到该链表的尾部就可以实现。直到链表只剩一个节点8。所以可以看出递归定义为：将第一个节点后面的子链表逆序，然后对该子链表做同样的操作。递归终止的条件为：递归下去，直到链表只剩一个元素为止。下面通过代码实现:

def RecursiveReverese(head):
    '''
    没有头节点
    '''
    #Recursive：递归  Reverese：逆序
    #先判断链表是否只有一个元素，是则返回上一层；是否为空，是则返回
    if head is None or head.next is None:
        return head
    else:
        #不为空，则递归逆序除第一个节点外的子链表
        newhead = RecursiveReverese(head.next)
        #前面当链表只有一个元素时返回了上一层，也就是说此时有两个元素。
        #将当前遍历到的节点链接到链表尾部
        head.next.next = head
        head.next = None
    return newhead

def Reverese(head):
    '''
    带头节点
    :param head: 带头节点链表
    :return: 逆序后的链表
    '''
    if head.next is None:
        return head
    #因为头节点没有数据，不需要参与逆序，所以从第一个节点开始逆序
    newhead=RecursiveReverese(head.next)
    head.next=newhead
    return head

处理函数就是这些，下面给个全部的代码：

#先建立节点对象LNode
class LNode:
    def __init__(self,arg):
        # 这是数据域data
        self.data = arg    
        # 这是节点的next域，也就是下一个节点的引用
        self.next = None  
"""
方法功能：创建一个带头节点的单链表
"""
def creatLink(x):
    #  x是链表的长度 
    i = 1
    head = LNode(None) # 先构造单链表的头节点
    tmp = None # 用来指向新添加的节点
    cur = head # 用来指向链表的最后一个节点
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head
def RecursiveReverese(head):
    '''
    没有头节点
    '''
    #Recursive：递归  Reverese：逆序
    #先判断链表是否只有一个元素，是则返回上一层；是否为空，是则返回
    if head is None or head.next is None:
        return head
    else:
        #不为空，则递归逆序除第一个节点外的子链表
        newhead = RecursiveReverese(head.next)
        #前面当链表只有一个元素时返回了上一层，也就是说此时有两个元素。
        #将当前遍历到的节点链接到链表尾部
        head.next.next = head
        head.next = None
    return newhead

def Reverese(head):
    '''
    带头节点
    :param head: 带头节点链表
    :return: 逆序后的链表
    '''
    if head.next is None:
        return head
    #因为头节点没有数据，不需要参与逆序，所以从第一个节点开始逆序
    newhead=RecursiveReverese(head.next)
    head.next=newhead
    return head

if __name__=='__main__':
    head = creatLink(8)
    cur = head.next
    #打印链表
    print("BeforeReversehead:")
    while cur is not None:
        print(cur.data)
        cur = cur.next
    #调用逆序函数
    head = Reverese(head)
    cur = head.next
    #打印逆序后链表
    print("AfterRevershead:")
    while cur is not None:
        print(cur.data)
        cur = cur.next

运行结果如下：