本文目录
定义
链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
由于不必须按顺序存储，链表在插入的时候可以达到 $O(1)$ 的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 $O(n)$ 的时间，而顺序表相应的时间复杂度分别是 $O(log n)$ 和 $O(1)$。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表有很多种不同的类型：单向链表，双向链表以及循环链表。
其中单链表的定义如下：
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
常见题目
合并两个有序链表
递归方法：
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
时间复杂度与空间复杂度均为$O(n+m)$。
迭代方法：
class Solution:
def mergeTwoLists(self, l1, l2):
# maintain an unchanging reference to node ahead of the return node.
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# exactly one of l1 and l2 can be non-null at this point, so connect
# the non-null list to the end of the merged list.
prev.next = l1 if l1 is not None else l2
return prehead.next
时间复杂度为$O(n+m)$，空间复杂度为$O(1)$。
反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 迭代
# if not head:
# return None
# prev, cur = None, head
# while cur:
# next = cur.next
# cur.next = prev
# prev, cur = cur, next
# return prev
# 递归
if head is None or head.next is None:
return head
node = self.reverseList(head.next)
head.next.next = head
head.next = None
return node
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head or not head.next or m == n:
return head
dummy = ListNode(0)
dummy.next = head
prev, cur = dummy, head
count = 1
while count <= n:
tmp = [cur, cur.next]
if count == m:
prev_start, start = prev, cur
elif count > m and count < n:
cur.next = prev
elif count == n:
start.next = cur.next
prev_start.next = cur
cur.next = prev
prev, cur = tmp
count += 1
return dummy.next
pre_start指向第m-1节点，start指向第m个节点。
两数相加
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
q = dummy
carry = 0
while l1 is not None or l2 is not None:
val1 = l1.val if l1 is not None else 0
val2 = l2.val if l2 is not None else 0
carry, digit = divmod(val1+val2+carry, 10)
q.next = ListNode(digit)
q = q.next
l1 = l1.next if l1 is not None else None
l2 = l2.next if l2 is not None else None
if carry > 0:
q.next = ListNode(carry)
return dummy.next
链表排序
题目描述：在 $O(nlogn)$的时间间复杂度和常数级空间复杂度下，对链表进行排序。
class Solution(object):
def merge(self, h1, h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next, tail, h1 = h1, h1, h1.next
else:
tail.next, tail, h2 = h2, h2, h2.next
tail.next = h1 or h2
return dummy.next
def sortList(self, head):
if not head or not head.next:
return head
# slow实际上是链表的中点，这部分代码将链表分割为两部分再进行归并排序
pre, slow, fast = None, head, head
while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None
return self.merge(*map(self.sortList, (head, slow)))
由于使用了递归，这里的空间复杂度实际上是$O(nlogn)$。
$O(1)$空间复杂度的解法比较复杂，可以参考：Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity
相交链表
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
# 哈希表存储访问过得节点
# visited = set()
# while headA:
# visited.add(headA)
# headA = headA.next
# while headB:
# if headB in visited:
# return headB
# headB = headB.next
# return None
# 第二种方法：使用两个指针，第一个指针从HeadA开始，
# 若遍历到终点，则从B的头部继续开始
# 同理，第二个指针从headB开始，遍历到终点时，从headA
# 继续遍历，容易知道，这两个指针会在交点相遇。
# 如果没有交点，则它们总有一个时刻都等于None
if not headA or not headB:
return None
A, B = headA, headB
while A!=B:
A = A.next if A else headB
B = B.next if B else headA
return A
环形链表
给定一个链表，判断链表中是否有环，返回True或者False。
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
# 使用哈希表，记录是否有重复出现的节点
# visited = set()
# while head:
# if head not in visited:
# visited.add(head)
# else:
# return True
# head = head.next
# return False
# 通过使用具有 不同速度 的快、慢两个指针遍历链表，可以降低空间复杂度
# 如果有环，那么slow与fast两个指针会在环上的某个点相遇(类似两个人在跑圈)
if not head or not head.next:
return False
slow, fast = head, head.next
while slow != fast:
if not fast.next or not fast.next.next:
return False
slow = slow.next
fast = fast.next.next
return True
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# O(n)空间复杂度
# visited = set()
# ind = 0
# while head:
# if head not in visited:
# visited.add(head)
# else:
# return head
# head = head.next
# return None
# 使用双指针 O(1)空间复杂度
if not head or not head.next:
return None
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
while head != slow:
head = head.next
slow = slow.next
return slow
移除链表元素
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy_head = ListNode(0)
dummy_head.next = head
q = dummy_head
while q.next is not None:
if q.next.val == val:
q.next = q.next.next
else:
q = q.next
return dummy_head.next
合并K个排序链表
利用优先队列：
from queue import PriorityQueue
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
dummy = ListNode(0)
cur = dummy
q = PriorityQueue()
for i, node in enumerate(lists):
if node:
q.put((node.val, i, node))
while q.qsize() > 0:
item = q.get()
cur.next, ind = item[2], item[1]
cur = cur.next
if cur.next:
q.put((cur.next.val, ind, cur.next))
return dummy.next
逐一两两合并链表：
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else None
def merge2Lists(self, l1, l2):
head = point = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l2.next
point = point.next
point.next = l1 or l2
return head.next