Java集合分析4

队列

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

习题

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

  2. 单链表的反转 

    
fun <E> Node<E>.printList() &#123;
    var r: Node<E>? = this
    while (r?.next != null) &#123;
        println(r.item)
        r = r.next
    &#125;
&#125;

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

  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. 找到单链表尾部, 尾部向前移动, 尾部始终是排好序的.

      实现

      //单链表的冒泡排序

fun <E: Comparable<E>> bubbleSort(head: Node<E>?): Node<E>? &#123;
    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) &#123;
        while (p != tail) &#123;
            if (p?.item != null && p.next?.item != null)&#123;
                if (p.item!! > p.next!!.item!!)&#123;
                    val temp = p.item
                    p.item = p.next!!.item
                    p.next!!.item = temp
                &#125;
                prev = p
                p = p.next
            &#125;
        &#125;
        tail = prev
        p = pHead
    &#125;
    return head

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

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

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

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

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

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

应用

阻塞队列

优先级队列

队列在并发里的应用

Comments

⬆︎TOP