Linked List

[ahasusie]

practice: 21, 206, 19, 141, 142, LinkedList.py

common mistakes:

1. don't forget to cur = cur.next
2. is Head a node or just a pointer?
   • can just be a pointer. next = prev = None
3. don't forget to deal with cur.next = None
4. be aware of index, the Nth node should be for i in range(1, N)
5. visit the tail
6. while cur: vs while cur.next:
   • if there will be operations about cur.next then must judge if cur is none.
   • if there will be operations about cur.next.next then must judge if cur.next is none
7. how to reserve "prev" node in single linked list?
8. pay attention to edge cases:
   • before head
   • after tail
   • empty linked list
   • value/node not found

dummy node:

1. when need to modify the head
2. when building a new linked list without knowing the head

[ahasusie]

two pointers

template:

1. Always examine if the node is null before you call the next field. Getting the next node of a null node will cause the null-pointer error. For example, before we run fast = fast.next.next, we need to examine both fast and fast.next is not null.

2. Carefully define the end conditions of your loop.

[ahasusie]

traversal insert/delete search detect loop sort reverse double linked list