Coding Pattern:

Linked List Manipulation

This pattern has an earnable cheat sheet.

Pattern concept

Step 1 of 31
Linked List Manipulation Slide 1: node1.val = 12 node1.next = None node1 = ListNode(12) A list node holds two important fields: a value (val) and a reference (next) to Non...
Linked List Manipulation Slide 2: node1.next = ListNode(5) A list node holds two important fields: a value (val) and a reference (next) to Non...
Linked List Manipulation Slide 3: node1.next.next = ListNode(8) A list node holds two important fields: a value (val) and a reference (next) to Non...
Linked List Manipulation Slide 4: A linked list is a chain of these nodes. linked list
Linked List Manipulation Slide 5: The head refers to the first node in the linked list and the tail refers to the las... head = node1
Linked List Manipulation Slide 6: Linked list questions often involve manipulating and tracking nodes by using pointe... curr = head
Linked List Manipulation Slide 7: For example, to delete the node next to curr, assign del to that node. Then point c... curr.next = del.next not accessible
Linked List Manipulation Slide 8: This is also equivalent to updating curr to point to the node after the next. curr.next = curr.next.next not accessible
Linked List Manipulation Slide 9: Sometimes it's helpful to create a dummy node at the head of the list so we can eas... dummy.next = head
Linked List Manipulation Slide 10: Use fast-slow pointers to detect cycles or find the middle node. For every 1 step s...
Linked List Manipulation Slide 11: Use fast-slow pointers to detect cycles or find the middle node. For every 1 step s...
Linked List Manipulation Slide 12: Whenfastreaches the tail,slow...
Linked List Manipulation Slide 13: If there were an even number of nodes, then slowwill be at the second middle node (... middle right!
Linked List Manipulation Slide 14: Consider this question:...
Linked List Manipulation Slide 15: Consider this question:...
Linked List Manipulation Slide 16: We need one pointer (curr) to track where we are in the linked list...
Linked List Manipulation Slide 17: ... and another pointer (prev) initialized to None which tracks the reversed part o...
Linked List Manipulation Slide 18: To reverse the list nodes, we could point curr to prev. However, we'd lose referenc... How do we access this?
Linked List Manipulation Slide 19: Therefore we need to temporarily save the next node (temp)...
Linked List Manipulation Slide 20
Linked List Manipulation Slide 21
Linked List Manipulation Slide 22
Linked List Manipulation Slide 23
Linked List Manipulation Slide 24
Linked List Manipulation Slide 25
Linked List Manipulation Slide 26
Linked List Manipulation Slide 27
Linked List Manipulation Slide 28
Linked List Manipulation Slide 29
Linked List Manipulation Slide 30: Once curr reaches the end of the list, we know the entire list has been reversed.
Linked List Manipulation Slide 31: prev is the new head of the reversed linked list, so return it.

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?

Note

Most linked list problems can be solved in O(n) time since they usually require one pass through the entire linked list.