链表代码
理解指针或引用的含义
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
警惕指针丢失和内存泄漏
执行插入删除操作时，一定得注意 操作顺序，及后续的处理。
image.jpeg
利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。 这里引入哨兵结点，在任何时候，不管链表是不是空，head指针都会指向这个哨兵结点。这种带哨兵结点的链表叫带头链表，没有哨兵结点的链表就叫做不带头链表。
哨兵结点不存储数据，因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以同一位相同的代码实现逻辑。
image.jpeg
重点留意边界条件处理
经常用的边界条件有：
如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
除此之外，就是不同场景下的一些特定边界条件。
举例画图，辅助思考：
image.jpeg
代码示例：
单链表翻转(206:. 反转链表)：
# 单链表定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverse_list(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
cur = self.reverse_list(head.next)
head.next.next = head
head.next = None
return cur
判断链表是否有环(141. 环形链表)：
# 单链表定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def have_cycle(self, head: ListNode) -> bool:
if head is None or head.next is None:
return False
slow = head
faster = head.next
while slow != faster:
if faster is None or faster.next is None:
return False
slow = slow.next
faster = faster.next.next
return True
返回链表中入环的第一个结点(142.环形链表 II)：
# 单链表定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detect_cycle(self, head: ListNode) -> ListNode:
visited = set()
node = head
while node:
if node in visited:
return node
else:
visited.add(node)
node = node.next
return None
合并两个有序链表(21. 合并两个有序链表)：
# 单链表定义
class ListNode:
def __init__(self, x=0):
self.val = x
self.next = None
class Solution:
def merge_two_lists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode()
temp = head
while l1 and l2:
if l1.val < l2.val:
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next
temp.next = l1 or l2
return head.next
合并 K 个有序链表：
import heapq
# 单链表定义
class ListNode:
def __init__(self, x=0):
self.val = x
self.next = None
class Solution:
def merge_k_lists(self, lists: [ListNode]) -> ListNode:
if not lists: return
queue = []
dummy = ListNode(-1)
cur = dummy
for i in range(len(lists)):
head = lists[i]
while head:
heapq.heappush(queue, (head.val, head))
head = head.next
while queue:
_, cur.next = heapq.heappop(queue)
cur = cur.next
cur.next = None
return dummy.next
剑指 Offer 18. 删除链表的结点：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val: return head.next
cur = head
while cur.next is not None and cur.next.val != val:
cur = cur.next
if cur.next is not None:
cur.next = cur.next.next
return head
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head is None:
return head
if head.val == val:
return head.next
head.next = self.deleteNode(head.next, val)
return head
链表的中间结点：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
cur = head
count = 0
while cur:
cur = cur.next
count += 1
middle = count//2
for i in range(middle):
head = head.next
return head
