介绍

List

我们首先谈谈列表 List：

  • 当我们知道列表的头指针p时，p指向列表第一个元素的地址
  • 当我们需要知道列表的第2个元素时，我们只需把头指针+1，即p+1指向第2个元素
  • 同理，p+i-1指向数组中第i个元素

也就是说，列表中元素的指针储存在一块连续的内存上，我们要知道下一个元素的指针时，只需将当前元素的指针后移一个单位即可。

链表

但链表不同，其中的元素本身就是一个指针：

  • 当我们知道链表的头指针p时，可以通过 p.val 取出第一个元素
  • p.next 直接储存了下一个元素的指针
  • 当我们遍历链表时，只需 p=p.next 即可

代码示例

通过代码来说明，能更清楚地感受，LeetCode上最经典的链表结构如下：

  1. class ListNode(object):
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None

那我们首先创建一个链表：

  1. # 创建 ListNode 格式的链表
  2. original_list=[1,2,3,4,5]
  3. head=ListNode(None)
  4. # 用p_head储存头指针
  5. p_head=head
  6. for i in original_list:
  7.     head.next=ListNode(i)
  8.     head=head.next
  9. head=p_head.next

链表的遍历也很简单：

  1. p=head
  2. while p:
  3.     print(p.val)
  4.     p=p.next

如果我们要删除链表中的元素，可以这样：

  1. def deleteNode(head, node):
  2.     # 储存头指针
  3.     p_head = head
  4.     while head:
  5.         if head.val == node:
  6.             head.val=head.next.val
  7.             head.next = head.next.next
  8.             return p_head
  9.         else:
  10.             head = head.next
  11.     return p_head

最终代码汇总：

  1. class ListNode(object):
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  6. def deleteNode(head, node):
  7.     # 储存头指针
  8.     p_head = head
  9.     while head:
  10.         if head.val == node:
  11.             head.val=head.next.val
  12.             head.next = head.next.next
  13.             return p_head
  14.         else:
  15.             head = head.next
  16.     return p_head
  19. original_list=[1,2,3,4,5]
  20. target=3
  22. # 创建 ListNode 格式的链表
  23. head=ListNode(None)
  24. p_head=head
  25. for i in original_list:
  26.     head.next=ListNode(i)
  27.     head=head.next
  28. head=p_head.next
  30. res=deleteNode(head,target)
  31. while res:
  32.     print(res.val)
  33.     res=res.next

237. 删除链表中的节点

模板

综合以上，写了一个单向链表的模板

  1. class ListNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  7. class SingleList:
  8.     def __init__(self, L) -> None:
  9.         self.head = ListNode(None)
  10.         self.len = len(L)
  11.         p = self.head
  12.         for i in L:
  13.             p.next = ListNode(i)
  14.             p = p.next
  15.         self.head = self.head.next
  17.     def GetiNode(self, i):
  18.         n = self.len
  19.         if i < 0 or i > n:
  20.             raise IndexError("Index {} > Length {}".format(i, n))
  21.         head = self.head
  22.         for _ in range(i):
  23.             head = head.next
  24.         return head
  26.     def Traversal(self, p=None):
  27.         if not p:
  28.             p = self.head
  29.         print("#"*10+" Traversal Start "+"#"*10)
  30.         while p:
  31.             print(p.val)
  32.             p = p.next
  34.     def DeleteNode(self, node):
  35.         head = self.head
  36.         while head:
  37.             if head.val == node:
  38.                 head.val = head.next.val
  39.                 head.next = head.next.next
  40.                 return
  41.             else:
  42.                 head = head.next
  45. if __name__ == "__main__":
  46.     original_list = [0, 1, 2, 3, 4, 5]
  47.     SList = SingleList(original_list)
  48.     SList.Traversal()
  49.     node = SList.GetiNode(3)
  50.     SList.Traversal(node)
  51.     SList.DeleteNode(4)
  52.     SList.Traversal()

输出结果为：

########## Traversal Start ##########
0
1
2
3
4
5
########## Traversal Start ##########
3
4
5
########## Traversal Start ##########
0
1
2
3
5

为了简化起见，省略了很多边界情况的讨论，更完备的代码请参看
707. 设计链表