Skills for tackling LeetCode problems - Inplace Reversal of a Linked List.
Inplace reversal is an efficient approach to reverse the links, using the existing node objects and without using extra memory.
1. Reverse a LinkedList
Given the head of a Singly LinkedList, reverse the LinkedList. Write a function to return teh new head of the reversed LinkedList.
# Time complexity O(N), where N is the total number of nodes. Space complexity O(1)
# class Node:
# def __init__(self, value, next=None):
# self.value = value
# self.next = next
def reverse(head):
pre, cur, nxt = None, head, None
while cur is not None:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre # return when cur = None, pre = newHead
2. Reverse a Sub-list
Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.
# Time complexity O(N). Space complexity O(1).
def reverse_sub_list(head, p, q):
if p == q: return head
cur, pre, nxt = head, None, None
i = 1
while cur is not None and i < p: # locate p
pre = cur
cur = cur.next
i += 1
pre_p = pre
at_p = cur
i = 0
while cur is not None and i < q - p + 1: # reverse p to q
nxt = cur.next
cur.next = pre
pre = cur # finally pre is at q
cur = nxt # finally cur is at post q
i += 1
# link q to previous part
if pre_p is not None:
pre_p.next = pre
else: # if pre_p is None, q = 1
head = pre
# link p to last part
at_p.next = cur
return head
3. Reverse every K-element Sub-list
Given the head of a LinkedList and a number k, reverse every k sized sub-list starting from the head. If in the end you are left with a sub-list with less than k element, reverse it too.
# Time complexity O(N). Space complexity O(1).
def reverse_every_k_elements(head, k):
if k <= 1 or head is None:
return head
cur, pre = head, None
while cur is not None:
pre_part = pre
at_part = cur
nxt = None
i = 0
while cur is not None and i < k: # reverse k nodes
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
i += 1
# connect with the previous part
if pre_part is not None:
pre_part.next = pre
else:
head = pre
# connect with the next part
at_part.next = cur
pre = at_part
return head
