【Python】递归之反转链表

反转链表（https://leetcode.cn/problems/reverse-linked-list/）

画个图

!!!注意：python自有的交换，千万不能写错顺序！！！！

可以分开写，但分开写需需要tmp进行暂存

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

反转相邻列表（https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/）

暴力破解法：

直接进行交换（也可以理解为反转），下面的k个一组反转需要引入一个计数器

 class Solution:
     def swapPairs(self, head: ListNode) -> ListNode:
         if not head:
             return 
         if not head.next:
             return head
         # 先进行第一次交换
         tmp = head.next
         head.next = tmp.next
         tmp.next = head
         ans = tmp
         # 交换后tmp即为头结点，后续继续交换就行，最后还是输出tmp
         while head.next:
             p = head.next 
             q = head.next.next
             if not q:
                 return ans
             head.next = p.next
             p.next = q.next
             head = q.next = p
 ​
         return ans

K个一组反转链表（https://leetcode.cn/problems/reverse-nodes-in-k-group/）

思路：

• 前k个反转，k+1 ~ 2k个反转...确定用递归
• 反转k个需要计数，画个图，head -> head.next -> ... -> cur -> head ->head.next，环形
• 当链表数量<k时，直接返回head
• 当链表数量>=k时，进行递归
• 递归体：
  • 进行反转，需要进行k次偏移，用count计数，具体偏移过程参考反转链表
  • 最后将反转链表后的头结点返回

最重要的就是画图，画图，画图

 class Solution:
     def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
         cur = head
         count = 0
         while cur and count < k:
             cur = cur.next
             count += 1            
         if count == k:
             cur = self.reverseKGroup(cur, k)
             while count:
                 head.next, head, cur = cur, head.next, head
                 count -= 1
             head = cur   
         return head