Overview
1
2
3
4
| class ListNode:
def __init__(self, x):
self.val = x
self.next = None
|
- Add a node into LinkedList is O(1).
- Remove a node from LinkedList is O(1) but search it is O(n).
Samples
Traversing and merge
No.2 - Add Two Numbers
Two pointers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p1, p2 = l1, l2
carry = 0
ans = ListNode(0)
p = ans
while p1 != None and p2 != None:
sum_ = p1.val + p2.val + carry
carry = 1 if sum_ >= 10 else 0
sum_ = sum_ if sum_ < 10 else sum_ - 10
p.next = ListNode(sum_)
p, p1, p2 = p.next, p1.next, p2.next
p1 = p1 if p1 != None else p2
while p1 != None and carry:
sum_ = p1.val + carry
carry = 1 if sum_ >= 10 else 0
sum_ = sum_ if sum_ < 10 else sum_ - 10
p.next = ListNode(sum_)
p, p1 = p.next, p1.next
p.next = p1
if carry == 1:
p.next = ListNode(1)
return ans.next
|
No.21 - Merge Two Sorted Lists
Several pointers.
No.23 - Merge k Sorted Lists
Priority queue
No.328 - Odd Even Linked List
Other basic function
No.237 - Delete Node in a Linked List
1
2
3
4
5
6
7
| def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
|
No.138 - Copy List with Random Pointer
Deep Copy
Recursively
No.206 - Reverse Linked List
No.234 - Palindrome Linked List
Combine with other data strucure
No.19 - Remove Nth Node From End of List
With List
No.206 - Reverse Linked List
Stack
No.141 - LinkeList List Cycle
HashTable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
p = head
se = set()
while(p != None):
if(p in se):
return True
else:
se.add(p)
p = p.next
return False
|
No.160 - Intersection of Two Linked Lists
HashTable
No.138 - Copy List with Random Pointer
HashTable