链表算法 篇二

合并K个有序列表

package com.algorithm202305.linkedlist;

import java.util.List;
import java.util.PriorityQueue;

/**
 * 合并K个有序链表
 * 合并K个有序链表的逻辑类似于合并两个有序链表，难点在于，如何快速得到K个节点中最小的节点，接到结果链表上
 * 这里我们就要用到优先级队列（二叉堆）这种数据结构，把链表节点放入一个最小堆，第一个节点设置为最小值
 */
public class Demo3 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(3);
        ListNode l6 = new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        ListNode l7 = new ListNode(2);
        ListNode l8 = new ListNode(6);
        l7.next = l8;
        ListNode[] listNodes = {l1, l4, l7};
        ListNode listNode = mergeKLists(listNodes);
        traverse(listNode);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

    static void traverse(ListNode node) {
        System.out.print(node.val + " ");
        if (node.next != null) {
            node = node.next;
            traverse(node);
        }
    }

    static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        //虚拟节点
        ListNode dummy = new ListNode(-1);
        //设置指针
        ListNode p = dummy;
        //
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
        //将K个链表的头节点加入最小堆（优先级队列）
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }
        while (!pq.isEmpty()) {
            //获取最小节点，接到结果链表中
            ListNode poll = pq.poll();
            p.next = poll;
            if (poll.next != null) {
                pq.add(poll.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
}

单链表的倒数第K个节点

只遍历一次链表，就算出倒数第 k 个节点。

1.首先，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步：

2.现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了对吧？

趁这个时候，再用一个指针 p2 指向链表头节点 head：

接下来就很显然了，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上：

这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。

package com.algorithm202305.linkedlist;

/**
 * 单链表的倒数第K个节点
 */
public class Demo4 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

    static void traverse(ListNode node) {
        System.out.print(node.val + " ");
        if (node.next != null) {
            node = node.next;
            traverse(node);
        }
    }

    // 返回链表的倒数第 k 个节点
    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
        return p2;
    }

}