Java集合分析4

Posted on Edited on In
队列

主要是一些习题吧, 队列也是比较简单的数据结构, 主要体现在应用上.

习题

  1. 数据结构与算法课后习题

  2. 单链表的反转 

    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

    fun <E> Node<E>.printList() {
        var r: Node<E>? = this
        while (r?.next != null) {
            println(r.item)
            r = r.next
        }
    }

    fun <E> revserSingleOriententList(head: Node<E>?) {
        var newHead = Node<E>(null, null, null)
        var cur = head
        while (cur != null) {
            var temp = cur.next
            cur.next = newHead
            newHead = cur
            cur = temp
        }
        newHead.printList()
    }
    fun test() {
        val head: Node<Int>? = Node(0, null, null)
        var x = head
        for (i in 1..9) {
            x?.next = Node(i, null, null)
            x = x?.next
        }
        revserSingleOriententList(head)
    }

  3. 判断链表是否带环；若带环，求环的长度和入口点

    1. **实现思路：**设置两个快慢指针分别指向链表的头节点，快指针一次走两步，慢指针一次走一步，如果两个相遇了，则单链表带环，如果快指针走到NULL节点，则链表不带环；

    2. **实现思路：**在判断单链表是否带环的问题中，我们找到了单环单链表的相遇结点，用于个指针从单链表的相遇结点开始走，并且设置一个计数器，每走一步，计数器加一，直到该指针再次遇到相遇点，则返回计数器的数；

  4. 遍历一次，找到中间节点; 快慢指针, 快的是慢的两倍.

  5. 遍历一次，找到倒数第 k 个结点（k从1开始）原理同上.

    1. 先让快指针走k-1步,然后两个指针一起走,直到快指针指向null了,此时慢指针指向倒数第k个节点.

  6. 遍历一次，删除倒数第 k 个结点（k从1开始），不能用替换删除法

    1. 找到倒数第k-1个节点, 即k的前一个节点, 让next节点指向k个节点的next即可

  7. 约瑟夫环 已经解决

  8. 单链表冒泡排序

    1. 找到单链表尾部, 尾部向前移动, 尾部始终是排好序的.

      实现

      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
      //单链表的冒泡排序

      fun <E: Comparable<E>> bubbleSort(head: Node<E>?): Node<E>? {
          val pHead = head;
          var tail: Node<E>? = pHead
          var p: Node<E>? = pHead
          var prev: Node<E>? = p
          while (tail?.next != null)
              tail = tail.next
          while (tail != pHead) {
              while (p != tail) {
                  if (p?.item != null && p.next?.item != null){
                      if (p.item!! > p.next!!.item!!){
                          val temp = p.item
                          p.item = p.next!!.item
                          p.next!!.item = temp
                      }
                      prev = p
                      p = p.next
                  }
              }
              tail = prev
              p = pHead
          }
          return head

  9. 合并两个有序链表 同交集并集

  10. 判断两个链表是否相交;相交则求交点(链表不带环)

  11. 先判断有无环, 如果一个有一个没有,则肯定不会相交

  12. 如果两个链表都没有环, 那么两个链表的尾结点肯定是交点

  13. 如果两个链表都有环 如果两个链表h1,h2都有环，则可以找到两个链表上并且在环上的任何一个结点p1和p2。如果从结点p1开始遍历链表h1，能够遍历到p2，说明两个链表相交；否则从p1开始遍历h1，遍历一圈后又回到p1，而未遍历到p2，说明两个链表不相交。

  14. 链表的交集, 并集等.

应用

阻塞队列

优先级队列

队列在并发里的应用