We will introduce in-place reversal of a linked list pattern, which is very useful to solve the problems involving reversal of a Linked List with the constraint that we need to do it in-place without using extra memory.
LeetCode 206 - Reverse Linked List [easy]
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULLclass Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node = head
prev = None
while node:
temp = node.next
node.next = prev
prev = node
node = temp
return prev
Time Complexity: O(N) where N is the number of nodes in the Linked Lists.
Space Complexity: O(1), algorithm runs in constant space.
When the problem gives this constraint and Linked Lists data structure, you should think about in-place reversal of a linked list pattern.
LeetCode 92 - Reverse Linked List II [medium]
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example: Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Reverse Linked List II Solution:
class Solution:
def reverse(self, head, left, right):
curr_node = head
next_node = curr_node.next
while left < right and next_node:
tmp = next_node.next
next_node.next = curr_node
curr_node = next_node
next_node = tmp
left += 1
return head, curr_node, next_node
def reverseBetween(self, head: [ListNode], left: int, right: int) -> [ListNode]:
if left == right:
return head
start = 1
start_node = head
prev_start = None
while start < left and start:
prev_start = start_node
start_node = start_node.next
start += 1
tail, header, tail_next = self.reverse(start_node, left, right)
if prev_start:
prev_start.next = header
else:
head = header
tail.next = tail_next
return head
LeetCode 25 - Reverse Nodes in k-Group [hard]
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. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example: Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
class Solution:
def reverseLinkedList(self, head, k):
new_head, ptr = None, head
while k:
next_node = ptr.next
ptr.next = new_head
new_head = ptr
ptr = next_node
k -= 1
return new_head
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
ptr = head
ktail = None
new_head = None
while ptr:
count = 0
ptr = head
while count < k and ptr:
ptr = ptr.next
count += 1
if count == k:
revHead = self.reverseLinkedList(head, k)
if not new_head:
new_head = revHead
if ktail:
ktail.next = revHead
ktail = head
head = ptr
if ktail:
ktail.next = head
return new_head if new_head else head
