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.
head of a singly linked list, reverse the list, and return the reversed list.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node = head
prev = None
temp = node.next
node.next = prev
prev = node
node = temp
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.
head of a singly linked list and two integers
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
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:
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)
prev_start.next = header
head = header
tail.next = tail_next
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
def reverseLinkedList(self, head, k):
new_head, ptr = None, head
next_node = ptr.next
ptr.next = new_head
new_head = ptr
ptr = next_node
k -= 1
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
ptr = head
ktail = None
new_head = None
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
ktail.next = revHead
ktail = head
head = ptr
ktail.next = head
return new_head if new_head else head