Linked List
Definition of singly-linked list.
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:
Search
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
Reverse Linkedlist
def reverseList(self, head):
new_head = None
while head:
p = head
head = head.next
p.next = new_head
new_head = p
return new_head
Tricks:
- 通常关于链表的题目，采用两个指针（two iterators）:
- 一前一后
- 一快一慢
- 使用dummy head
dummy = ListNode(0) dummy.next = head
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)