Reverse a Linked List

def reverse(head):
  
  prev = None

  while head:
    next = head.next
    head.next = prev
    prev = head
    head = next
  return prev

Reverse a Sublist

First need to skip to position p (skip p-1 Nodes). Keep track of the end of the first part, node at position p (becomes end of sublist).

Then, reverse nodes from position p to position q (q - p + 1 nodes). After reversal, current becomes the beginning of second part, and prev becomes to beginning of the sublist.

Lastly, connect the first part and second part with the sublist accordingly.

For related questions, we can call this function multiple times with different values of p and q.

# p and q are positions
def reverse_sub_list(head, p, q):

  # Cannot Reverse a sublist with length <= 1
  if q <= p:
    return head

  current = head
  prev = None
  i = 0

  # Skip First p-1 Nodes
  while current is not None and i < (p - 1):
    prev = current
    current = current.next
    i += 1

  # Save End of the first part and Beginning of sublist, 
  # which will become the end
  end_of_first_part = prev
  end_of_sublist = current


  # Reverse the sublist of length (q - p) + 1
  i = 0
  next = None

  while current is not None and i < ((q - p) + 1):
    next = current.next
    current.next = prev
    prev = current
    current = next
    i += 1
  
  # Prev is now the beginning of sublist
  # Current is the first node after the sublist
  beginning_of_sublist = prev
  beginning_of_second_part = current

  # Set end_of_sublist's next to the next part
  end_of_sublist.next = beginning_of_second_part

  # If end_of_first_part is None, then the reversal starts with
  # the head (p = 1)
  if end_of_first_part is not None:
    end_of_first_part.next = beginning_of_sublist
  else:
    head = beginning_of_sublist
  
  return head

Reverse every K-element Sub-List

Similar to above. Except we loop forever and break when current is None. Have to keep track of end_of_previous and end_of_sublist each loop so that we can make the appropriate links after reversing sublist.

def reverse_every_k_elements(head, k):
  
  if k <= 1 or head is None:
    return head
  
  previous = None
  current = head

  # Loop Forver (until we break)
  while True:
    # Save off last node of previous section
    # and end of current sub-list (once reversed)
    head.print_list()
    last_of_previous = previous
    last_of_sublist = current

    i = 0

    # Reverse the sublist of length k
    while current is not None and i < k:
      next = current.next
      current.next = previous
      previous = current
      current = next
      i += 1
    
    # Connect Previous Section to Sublist
    # If Sublist started with head, then set head
    if last_of_previous is not None:
      last_of_previous.next = previous
    else:
      head = previous

    # Connect end of sublist to next section
    last_of_sublist.next = current

    # If no more nodes (current loop ended at None)
    if current is None:
      break

    # Set previous for next loop
    previous = last_of_sublist

  return head

Reverse Alternating k-element Sublists

Very similar to above, except after reversing, skip k nodes. Also, makes more sense to use while current is not None instead of while True

def reverse_alternate_k_elements(head, k):
  if head is None or k <= 1:
    return head

  previous = None
  current = head

  while current is not None:
    # Store Last Node of Previous Section
    # Store Last Node of Sublist
    last_of_previous = previous
    last_of_sublist = current

    i = 0
    # Reverse k nodes
    while current is not None and i < k:
      next = current.next
      current.next = previous
      previous = current
      current = next
      i += 1

    # Connect previous section to sublist
    if last_of_previous is None:
      head = previous
    else:
      last_of_previous.next = previous
    
    # Connect sublist to next section
    last_of_sublist.next = current

    i = 0
    # Skip k nodes
    while current is not None and i < k:
      previous = current
      current = current.next
      i += 1

  return head

Rotate a Linked List

A little different than other reversing problems. Instead, we just have to skip length - rotations nodes, and set the head and last_node accordingly.

def rotate(head, rotations):
  
  if head is None or head.next is None or rotations < 1:
    return head

  last_node = head
  list_length = 1
  # Get length of list
  while last_node.next is not None:
    last_node = last_node.next
    list_length += 1

  # No need to do more than list_length rotations
  rotations %= list_length

  # Go ahead connect last node to head to make circular list
  last_node.next = head

  last_of_rotated = head
  skip_length = list_length - rotations
  # Now need to get new last node and new head
  for i in range(skip_length - 1):
    last_of_rotated = last_of_rotated.next

  # Set the new head
  # Set the last skipped node's next to None
  head = last_of_rotated.next
  last_of_rotated.next = None

  return head