当前位置： 移动技术网 > IT编程>脚本编程>Python > 单链表反转(python)

单链表反转(python)

2020年07月30日  | 移动技术网IT编程  | 我要评论

206.单链表反转

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

单向链表定义

单向链表也叫单链表，是链表中最简单的一种形式。每个节点包含两个域，一个信息域（元素域）和一个链接域。链接域存放下一节点的位置（python中的标识），最后一个节点的链接域指向一个空值。
来源：https://blog.csdn.net/m0_49180275/article/details/107508408

1）迭代思想

解题思路

  • 利用双指针不断在head上面向后移动，移动时先移动pre指针，然后cur指针cur.next,pre,cur = pre,cur,cur.next。
  • 要将链表反转，cur 指针表示当前遍历到的节点，pre 指针表示当前节点的前驱节点；中间变量 temp 保存当前节点的后驱节点。

1. 首先将pre指针指向Null，cur指针指向头节点head
2. 当cur!=Null时，执行循环
a. cur.next保存在temp中，防止链表丢失：temp=cur.next
b. 将cur.next指向前驱节点pre：cur.next=pre
此时cur节点中链接域存放的地址指向节点pre，即Null.
c. 将pre向后移动一位，即cur位置：pre=cur
d. 将cur向后移动一位，即temp位置：cur=temp
e. 以此不断循环，每一步循环中，都将原列表中cur.next链接域存放的地址指向其前一个节点，直至cur=Null，pre指向最后一个节点.
3. 返回pre：循环后，原链表中，最后一个节点中指向的下一个节点为原倒数第二个节点，以此类推，原列表的第一个节点指向Null；pre即相当于头节点，返回pre，相当于将原链表反转。
图解流程
反转链表迭代图解
来自：https://leetcode-cn.com/problems/reverse-linked-list/solution/tu-jie-liu-cheng-python3die-dai-xiang-jie-by-han-h/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
            #cur.next,pre,cur = pre,cur,cur.next
        return pre

2）递归思想

解题思路
head.next==None：到达尾部节点
head == None：输入空列表，直接返回空列表
递的操作
1.得到尾部节点:p = self.reverseList(head.next)
2.翻转当前节点：head.next.next = head
3.拆掉当前节点的next：head.next = None

为得到翻转后的链表，首先将head指针指向原链表的最后一个节点，并将其存储在节点p中，防止丢失，通过移动head.next指向的节点实现链表的翻转，最后返回p节点，即完成链表翻转。
递归过程：计算机中如何运行递归函数
使用递归时要考虑堆栈的使用情况。
在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。计算机会逐个弹出进行处理。
在这里插入图片描述
来源：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #递归结束条件，如果不存在节点或者只有一个节点时，返回节点本身
        if head == None or head.next==None:
            return head
        
        #处理head节点外的其它节点，将head.next指向链表中最后一个节点，触发函数终止条件，返回p=head.next
        #即head为倒数第2个节点，p=head.next为最后一个节点
        p=self.reverseList(head.next)
        
        #head的下一个节点指向head，实现翻转
        head.next.next=head
        #防止循环指向（双重指向）
        head.next= None
        return p
        #return head

return p 返回翻转后的链表
return head，结果为head=1
【递归操作存惑】仅能理解到if语句中return head，head=4，p=5，再执行head.next.next=head,head.next=None

本文地址：https://blog.csdn.net/weixin_45518182/article/details/107645218

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网