欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单链表反转(python)

程序员文章站 2023-12-29 11:35:46
反转一个单链表。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL单向链表定义单向链表也叫单链表,是链表中最简单的一种形式。每个节点包含两个域,一个信息域(元素域)和一个链接域。链接域存放下一节点的位置(python中的标识),最后一个节点的链接域指向一个空值。来源:https://blog.csdn.net/m0_49180275/article/details/107508408解题...

示例:
输入: 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,相当于将原链表反转。
图解流程
单链表反转(python)
来自: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节点,即完成链表翻转。
递归过程:计算机中如何运行递归函数
使用递归时要考虑堆栈的使用情况。
在一个函数中调用一个函数时,计算机需要在进入被调用函数之前跟踪它在当前函数中的位置(以及任何局部变量的值),通过运行时存放在堆栈中来实现(堆栈帧)。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后,他会弹出堆栈顶部元素,以恢复在进行函数调用之前所在的函数。计算机会逐个弹出进行处理。
单链表反转(python)
来源: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

上一篇:

下一篇: