Each node contains two fields: val, next.

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None


# Operations

Insertion & Deletion cost $$O(1)$$ time. While search costs $$O(n)$$ time, where $$n$$ is the length of the list. Basic operations of linked list can be defined with functions:

def search_list(L,key):
while L and L.val != key:
L = L.next
return L


## Insertion

def insert_after(node, new_node):
new_node.next = node.next
node.next = new_node


## Deletion

def delete_after(node):
node.next = node.next.next


def reverseList(self, head):


# Tricks:

• 通常关于链表的题目，采用两个指针（two iterators）:
• 一前一后
• 一快一慢
  dummy = ListNode(0)


# Problems

Problems listed in the order of difficulty. * denotes in top interview questions.

## Easy

• 019 019 Remove Nth Node From End of List * (note)
• 141 Linked List Cycle * (note)
• 206 Reverse Linked List * (note)
• 234 Palindrome Linked List * (note)
• 237 Delete Node in a Linked List * (note)

## Medium

• 092 Reverse a single sublist * (note)
• 021 Merge Two Sorted Lists * (note)