Python3--反转链表之迭代，递归，穿针引线(头插法)

╰半夏微凉° 2022-10-23 02:57 150阅读 0赞

# 递归法 #

[反转链表1][1]  
![在这里插入图片描述][20210318135300651.gif_pic_center]

class Solution(object):
    	def reverseList(self, head):
    		"""
    		:type head: ListNode
    		:rtype: ListNode
    		"""
    		# 递归终止条件是当前为空，或者下一个节点为空
    		if(head==None or head.next==None):
    			return head
    		# 这里的cur就是最后一个节点
    		cur = self.reverseList(head.next)
    		# 这里请配合动画演示理解
    		# 如果链表是 1->2->3->4->5，那么此时的cur就是5
    		# 而head是4，head的下一个是5，下下一个是空
    		# 所以head.next.next 就是5->4
    		head.next.next = head
    		# 防止链表循环，需要将head.next设置为空
    		head.next = None
    		# 每层递归函数都返回cur，也就是最后一个节点
    		return cur

# 迭代(双指针) #

[反转链表1][1]  
![在这里插入图片描述][20210318135315447.gif_pic_center]

class Solution(object):
    	def reverseList(self, head):
    		"""
    		:type head: ListNode
    		:rtype: ListNode
    		"""
    		# 申请两个节点，pre和 cur，pre指向None
    		pre = None
    		cur = head
    		# 遍历链表，while循环里面的内容其实可以写成一行
    		# 这里只做演示，就不搞那么骚气的写法了
    		while cur:
    			# 记录当前节点的下一个节点
    			tmp = cur.next
    			# 然后将当前节点指向pre
    			cur.next = pre
    			# pre和cur节点都前进一位
    			pre = cur
    			cur = tmp
    		return pre

# 穿针引线(头插法) #

[反转链表2][2]  
下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

curr：指向待反转区域的第一个节点 left；  
next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；  
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70_pic_center]  
操作步骤：

1.  先将 curr 的下一个节点记录为 next；
2.  执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
3.  执行操作 ②：把next 的下一个节点指向 pre 的下一个节点；
4.  执行操作 ③：把 pre 的下一个节点指向 next。

class Solution:
        def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
            # 设置 dummyNode 是这一类问题的一般做法
            dummy_node = ListNode(-1)
            dummy_node.next = head
            pre = dummy_node
            for _ in range(left - 1):
                pre = pre.next
    
            cur = pre.next
            for _ in range(right - left):
                next = cur.next
                cur.next = next.next
                next.next = pre.next
                pre.next = next
            return dummy_node.next

[1]: https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
[20210318135300651.gif_pic_center]: /images/20221022/12cbc37045364a7c822462d661876a5a.png
[20210318135315447.gif_pic_center]: /images/20221022/dcf2bd2b375f492ea7f3d02348cc7e9d.png
[2]: https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/8d5e2ac59d4b44a9b87661845eebab2d.png