Leetcode pattern: In-place Reversal of Linked List
Main Ideas
Most solutions use these 3 blocks:
i) Dummy nodes: Help us deal with edge cases
ii) Pointers
ii) Reverse Linked List
When solving a problem, think: how can I use these 3 blocks?
How to study
- Learn how to reverse linked list by solving Leetcode #206 (Make sure you know this so well that you can do it with your eyes closed)
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 2 pointers
prev, cur = None, head
# reverse linked list
while cur:
temp = cur.next
# reverse direction of CURRENT node
cur.next = prev
# move prev pointer one step
prev = cur
# move cur pointer one step
cur = temp
return prevNOTE: Linked list only changes when node.next = otherNode, it does not change on other expressions.
2. Learn how to use all 3 blocks by solving Leetcode #92
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
# 3 pointers
# leftPrev: once finish looping point to node before left
leftPrev, cur = dummy, head
prev = None
# 1) traverse until reaches left node
for i in range(left-1):
# reassign pointer
leftPrev, cur = cur, cur.next
# 2) reversing the linked list
# Now cur points to left node and leftPrev points to node before left
for i in range(right-left+1):
temp = cur.next
cur.next = prev
prev = cur
cur = temp
# 3) Update pointers
# intially leftPrev.next.next points to NULL
# cur is node after right
leftPrev.next.next = cur
# prev is right node
leftPrev.next = prev
return dummy.next