Reverse Nodes in k-Group — LeetCode 25 Python Solution
HardRecursionLinked List
- Problem
- #25
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list.
Example
- Input
- head = [1,2,3,4,5], k = 2
- Output
- [2,1,4,3,5]
Python solution
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
cur = head
while cur:
nxt = cur.next
cur.next = dummy.next
dummy.next = cur
cur = nxt
return dummy.next
dummy = pre = ListNode(next=head)
while pre:
cur = pre
for _ in range(k):
cur = cur.next
if cur is None:
return dummy.next
node = pre.next
nxt = cur.next
cur.next = None
pre.next = reverse(node)
node.next = nxt
pre = node
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the linked list |
| Space | O(1) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 25. Reverse Nodes in k-Group is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
On study lists
This problem is on NeetCode 150 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 25. Reverse Nodes in k-Group?
- LeetCode 25. Reverse Nodes in k-Group is rated Hard on LeetCode.
- What is the time complexity of LeetCode 25. Reverse Nodes in k-Group?
- The Python solution on this page runs in O(n), where n is the length of the linked list.
- What is the space complexity of LeetCode 25. Reverse Nodes in k-Group?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 25. Reverse Nodes in k-Group cover?
- LeetCode 25. Reverse Nodes in k-Group is tagged Recursion and Linked List on LeetCode.