203. 移除链表元素
- 思路
- example
- dummyhead 方便删除表头
- 赋值细节
移除：dummyhead
pre, cur, nxt
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummyhead = ListNode(-1, head)
cur = dummyhead
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummyhead.next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummyhead = ListNode(-1, head)
pre, cur = dummyhead, head
while cur:
if cur.val == val:
pre.next = cur.next
cur = pre.next
else:
pre = cur
cur = cur.next
return dummyhead.next
707. 设计链表
- 思路
- example
- singly LinkedList
- dummyhead
- self.head = Node(0)
- self.size = 0
- update self.size
- addAtIndex, deleteAtInex: move cur to Index-1 position
def __init__(self, val): dummyhead, size
addAtIndex() ---> addAtHead(), addAtTail()
需要找到pre
deleteAtIndex()
需要找到pre
- 复杂度. 时间：O(n), 空间: O(1)
更新self.size
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.head = Node(-1, None) # dummyhead
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
cur = self.head
for _ in range(index+1):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
cur = self.head
for _ in range(index):
cur = cur.next
temp = cur.next
cur.next = Node(val, None)
cur.next.next = temp
self.size += 1 # !!!
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
cur = self.head
for _ in range(index):
cur = cur.next
cur.next = cur.next.next
self.size -= 1 # !!!
- Doubly LinkedList
- use pre and cur
- get_node function
- update function
- check typos
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
class MyLinkedList:
def __init__(self):
self.head, self.tail = Node(0), Node(0)
self.head.next, self.tail.prev = self.tail, self.head
self.size = 0
def get_node(self, index: int) -> Node:
if index >= self.size // 2:
cur = self.tail
for _ in range(self.size-index):
cur = cur.prev
else:
cur = self.head
for _ in range(index+1):
cur = cur.next
return cur
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
cur = self.get_node(index)
return cur.val
def update(self, prev: Node, next: Node, val: int) -> None:
self.size += 1
node = Node(val)
prev.next, next.prev = node, node
node.prev, node.next = prev, next
def addAtHead(self, val: int) -> None:
self.update(self.head, self.head.next, val)
def addAtTail(self, val: int) -> None:
self.update(self.tail.prev, self.tail, val)
def addAtIndex(self, index: int, val: int) -> None:
if index < 0:
index = 0
elif index > self.size:
return
node = self.get_node(index)
self.update(node.prev, node, val)
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
node = self.get_node(index)
self.size -= 1
node.prev.next, node.next.prev = node.next, node.prev
206. 反转链表
- 思路
- example
- 迭代法，pre->cur->next
- 循环终止条件
- 检查边界：head, tail, None
pre, cur, nxt
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
-
递归法, 空间：O(n)
- 注意处理None list.
- head.next still points to newHead.tail
- 不要忘记处理new list的尾部，i.e., head.next = None
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(head):
if head == None or head.next == None:
return head
reversed_head = reverse(head.next)
head.next.next = head
head.next = None
return reversed_head
return reverse(head)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None # !!!
return newHead
