Coding Pattern:
Linked List Manipulation
This pattern has an earnable cheat sheet.
Pattern concept
Step 1 of 31
Use ← → arrow keys
Code snippets
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Reverse the linked list in-place.
def reverse_list(head: ListNode) -> ListNode: # Return early if the list is empty or has only one node.
if not head or not head.next:
return head
prev = None # Pointer to previous node.
curr = head # Pointer to current node.
while curr:
temp = curr.next
# Reverse the current node.
curr.next = prev
# Update the pointers.
prev = curr
curr = temp
return prev # Return the head of the reversed list.
How to identify
Does the problem involve any of these?
- Reversing or rearranging the nodes in the linked list
- Swap Nodes in Pairs: Swap nodes.
- Reverse Linked List II: Reverse nodes.
- Rotate List: Rotate nodes.
- Palindrome Linked List: Reverse or rearrange nodes.
- Removing or adding nodes at specific positions in the list
- Remove Repeats from Sorted List: Remove duplicates.
Note
Most linked list problems can be solved in O(n) time since they usually require one pass through the entire linked list.