1 month, 1 week

# Coding Patterns: In-place Reversal of a Linked List

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.

## Problem: Reverse Linked List

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 -> NULL``````

Solution:

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
while node:
temp = node.next
node.next = prev
prev = node
node = temp
return prev

Time ComplexityO(N) where `N` is the number of nodes in the Linked Lists.

Space ComplexityO(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.

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):
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
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:
else:
tail.next = tail_next

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]

Solution:

class Solution:
while k:
next_node = ptr.next
ptr = next_node
k -= 1
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
ktail = None
while ptr:
count = 0
while count < k and ptr:
ptr = ptr.next
count += 1
if count == k:
if ktail:
if ktail:

#### Responses(0)  Related