关于链表

Posted on | Edited on | In ,

虽然链表是一种比较基础的数据结构，但是在实际应用的时候用处没有那么多

  • 链表是一种线性的表，但是不会线性的存储数据
  • 数组存储的时候需要连续存储

单向链表

有一个头结点head，指向链表内存的首地址。
链表里面的每个节点有两个成员

  • 需要保存的数据val
  • 指向下一个结构的指针next

特点：

  • 查找
    • 对各个点的查找必须从头找起，后续的地址是前节点给出来的。无论访问哪个点都必须从头来
    • 时间复杂度n，和数组相同
  • 插入和删除（优势）
    • 由于链表是不连续的存储，所以在插入和删除的时候，链表不需要大量成员的位移
    • 复杂度1
  • 读取（劣势）
    • 数组因为连续存储，所以可以通过寻址迅速的定位。但是链表不连续，所以必须依据指针持续的遍历

应用

  • 由于有双向链表，单向链表的应用比较少
  • 撤销功能：文本，图形编辑器。用到了链表的删除特性
  • 实现图或者hashMap等高级数据结构

双向链表

增加了一个prev节点，相当于多了一个指针，所以用双向链表占的内存更多
比如编辑器的undo/redo操作，用双向链表就更好一点。如果是单向的话时间会是n

循环链表

链表的末尾指针指向了链表开头
比如分时装置

  • CPU处理多个用户的请求时产生抢占资源的情况，需要分时策略
  • 每个用户代表一个节点，会给每个节点分配一定的处理时间，然后进入下一个节点。

Leetcode链表练习题

141 判断单链表是否有cycle

思路：

  • in-place的方法，如果两个人一起跑步，一个快一个慢，那么总有一个时刻快的会把慢的套圈
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            fast = head
            slow = head
            while slow and fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if fast == slow:
                    return True
            return False

24 交换两个相邻的node

思路：

  • 注意这个node的交换，不单和目前的部分（目前操作的两个）有关系，还和前面一个点有关系，因为前面一个点的next需要是交换之前的后一个点
  • 注意while时候的条件判断，必须两个点都在的时候才能进行交换
  • 注意d这个附加的点，用这个点可以快速的定位head点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        counter = 0
        d = ListNode(-1)
        d.next = head
        prev_node = d
        while head and head.next:
            curr = head
            to_swap = head.next
            
            prev_node.next = to_swap
            curr.next = to_swap.next
            to_swap.next = curr
            
            prev_node = curr
            head = curr.next
            
        return d.next

328 把链表的odd位都交换到前面去

思路：

  • 判断这个点如果是odd，那么上一个odd的next是现在的点，这个点的下一个指向even的开始点
  • 如果这个点是even，那么上一个even的next是现在的点，这个点的下一个是null
  • 死磕了一个小时的原因：
    • 注意深拷贝和浅拷贝的问题，浅拷贝的时候，改变这个东西的同时，之前的也会改变
    • 注意形成环的问题，一定要注意每个点的input和output的方向都确定了，该赋值0的时候赋值0
    • 注意每次的odd点都应该指向even的起始点
    • 在下一个点会变化的时候，记得及时保存
      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
      27
      28
      29
      30
      31
      32
      33
      34
      35
      class Solution:
          def oddEvenList(self, head: ListNode) -> ListNode:
              start = ListNode(-1)
              even_start = ListNode(-1)
              start.next = head
              
              if (not head) or (not head.next): return head
              
              prev_odd = head
              prev_even = head.next
              even_start.next = prev_even
              
              
              counter = 1
              while head:
                  curr = head
                  if counter >=3:
                      temp = curr.next
                      if counter % 2 != 0: #odd
                          prev_odd.next = curr
                          curr.next = even_start.next
                          if counter == 3:
                              even_start.next.next = None
                          prev_odd = curr
                      elif counter % 2 == 0:#even
                          prev_even.next = curr
                          prev_even = curr
                          curr.next = None
                      head = temp
                  else:
                      head = curr.next
                  counter += 1
                  
              
              return start.next