【leedcode.25：Reverse Nodes in k-Group】 每k个节点反转_递归非递归4种解法

目录

 

题目：

解法一：递归改变节点连接

解法二：尾插法：

解法三：使用辅助空间，这里使用栈

解法四：递归交换值，不改变链表连接

---

题目：

 

解法一：递归改变节点连接

           思路：1.采用分治思想，从后往前递归，调用递归函数传进去下一个k部分的头结点和k，递归结束是节点为空，此时count 不为0，递归返回最后这部分(不管是否满k个节点)的头结点；
                      2.反转操作是从后往前，倒数第二部分head指向最后一部分head(递归返回)，依次在倒数第二部分进行k次反转，return head（反转后的head）

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
 
        if not head:
            return
 
        cur = head
        count = k
        while count and cur: # 循环结束，cur指向下一段Head；边界情况(1,2,3,4,5,6）,第二次调用函数传入head=4,k=3,返回是cur=none,k=3,所以会有第三次调用函数
            cur = cur.next
            count -= 1
        
        if count:
            return head
 
        next_head = self.reverseKGroup(cur, k) 
 
        while k:
            third = head.next
            head.next = next_head
            next_head = head
            head = third
            k -= 1
        
        return next_head

 

 解法二：尾插法：

        思路：1.从前往后，找到第k个节点tail，依次把第一个节点插入到tail后面；

                   2.再连接下一段，初始化head

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
 
        if not head:
            return head
        
        dummy = ListNode(0)  # 链表变化后不好找head的可以定义一个dummy结点
        dummy.next = head
        tail = dummy.next
        pre = dummy
 
        while True:
            count = k
            while count > 1 and tail:  # 找到第k个作为tail
                tail = tail.next
                count -= 1
 
            next_pre = pre.next  # 没反转前的第一个节点为反转后的结束节点，即下一次循环时pre更新的位置
            if not tail: break   # 如果当前循环不存在tail,说明到达最后一部分不满足k个节点
 
            while pre.next != tail: # 当pre的下一个节点不为tail,循环把pre的下一个节点移动到tail后面(移动一个节点到其他节点前或后)
                cur = pre.next 
                pre.next = cur.next
                cur.next = tail.next
                tail.next = cur
            pre = next_pre  # 一个k部分的节点移动结束，初始化pre,tail
            tail = pre.next
        return dummy.next

 

解法三：使用辅助空间，这里使用栈

       思路：

               1.从前往后遍历k个节点先存入栈中，当最后一部分不满足k个节点时，倒数第二部分尾节点指向，最后一部分头结点

               2.出栈依次连接，更新指针

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
 
        if not head:
            return
 
        dummy = ListNode(0)
        dummy.next = head
        cur = head
        p = dummy
 
        while True:
            stack = []
            while k and cur:  # 跳出循环是,cur是第k+1个节点
                stack.append(cur)
                cur = cur.next
                k -= 1
 
            if k > 1: 
                p.next = cur  # 最后一段不满k个节点，则前一部分最后一个节点指向最后一部分的head节点
                break
            
            while stack:
                p.next = stack.pop()
                p = p.next
 
            p.next = cur 
        
        return dummy.next

解法四：递归交换值，不改变链表连接

       思路： 每k个部分使用left,right指针，交换值，来完成反转

        TODO:递归交换值,代码满足类似1,2,3,4,5 k=2,3;  但是不满足1,2,3,4  k=4情况

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
 
        if not head:
            return 
        if k == 1:
            return head
 
        def reverse_detailed(cur, k):
            nonlocal stop, left, right
 
            if k < 2 or not right:
                return 
 
            right = right.next
            if not right:
                return 
 
            tail = reverse_detailed(right,k-1)
 
            if not right:
                return
 
            if k == 2:
                tail = right
 
            if left == right or right.next == left:
                stop = True
                return tail
                
            if not stop:
                left.val, right.val = right.val, left.val
 
            left = left.next
            return tail
 
        cur = head
        while cur:
            if not cur:  # 循环更新了cur
                return 
            stop = False
            left = right = cur
            tail = reverse_detailed(cur, k)
            if tail:
                cur = tail.next
            else:
                return head
            
        return head