[Leetcode][python]Reverse Nodes in k-Group/k个一组翻转链表

分手后的思念是犯贱 2022-06-09 11:35 114阅读 0赞

## 题目大意 ##

将一个链表中每k个数进行翻转，末尾不足k个的数不做变化。

## 解题思路 ##

参考：  
[https://shenjie1993.gitbooks.io/leetcode-python/025 Reverse Nodes in k-Group.html][https_shenjie1993.gitbooks.io_leetcode-python_025 Reverse Nodes in k-Group.html]  
A->B->C->D->E，现在我们要翻转BCD三个节点。进行以下几步：  
1.C->B  
2.D->C  
3.B->E  
4.A->D  
5.返回及节点B

## 代码 ##

class Solution(object):
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            if not head or k <= 1:
                return head
            dummy = ListNode(0)
            dummy.next = head
            current = dummy
            while current:
                current = self.reverseNextK(current, k)
            return dummy.next
    
        def reverseNextK(self, head, k):
            # Check if there are k nodes left
            current = head
            for i in range(k):
                if not current.next:
                    return None
                current = current.next
    
            # The last node when the k nodes reversed
            node = head.next
            prev = head
            curr = head.next
            # Reverse k nodes
            for i in range(k):
                nextNode = curr.next
                curr.next = prev
                prev = curr
                curr = nextNode
            # Connect with head and tail
            node.next = curr
            head.next = prev
            return node

## 总结 ##

太绕了

[https_shenjie1993.gitbooks.io_leetcode-python_025 Reverse Nodes in k-Group.html]: https://shenjie1993.gitbooks.io/leetcode-python/025%20Reverse%20Nodes%20in%20k-Group.html