本文主要是介绍单链表算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点

单链表反转

public class Test {
    // 单链表遍历
    public static void ergodic(Node curr){
        while(curr != null){
            System.out.print(curr.item);
            curr = curr.next;
        }
        System.out.println();
    }
    // 单链表反转
    public static Node reverse(Node list) {
        // 将 list 标为 当前节点，并 初始化 前节点 pre 为 null
        Node curr = list, pre = null;
        // 当前节点为 null 时，则退出循环
        while(curr != null){
            // 将 当前节点 的 后节点 保存到 next
            Node next = curr.next;
            // 将 前节点pre 标记为 当前节点 的 后节点
            curr.next = pre;
            // 将 当前节点 标记为 前节点
            pre = curr;
            // 将 next 标记为 当前节点
            curr = next;
        }
        return pre;
    }
    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(1,null);
        Node<Integer> node2 = new Node<>(2,node1);
        Node<Integer> node3 = new Node<>(3,node2);
        Node<Integer> node4 = new Node<>(4,node3);
        ergodic(node4);
        Node reverse = reverse(node4);
        ergodic(reverse);
    }
}

class Node<E> {
    E item;       // 当前元素的值
    Node<E> next; // 指向下一个元素

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

链表中环的检测

快慢指针：

• 无终点长跑中，如果直线跑，快慢两个人的距离会越来越大，不可能相遇，
• 如果绕环跑，则快慢两个人必然相遇

public class Test {
    // 检测环
    public static boolean checkCircle(Node list) {
        // 链表为 null 直接返回 false
        if(list == null) return false;
        // 初始化快慢指针
        Node fast = list.next, slow = list;
        // 如果无环，则 快指针 先到 尾结点
        while(fast != null && fast.next != null){
            // 快指针 一步 跑 两格
            fast = fast.next.next;
            // 慢指针 一步 跑 一格
            slow = slow.next;
            // 如果 快慢指针 相遇，则说明有环，如果无环，则 快指针 先到 尾结点
            if(fast == slow) return true;
        }
        // 快指针 已经 到了 尾结点
        return false;
    }
    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(1,null);
        Node<Integer> node2 = new Node<>(2,node1);
        Node<Integer> node3 = new Node<>(3,node2);
        Node<Integer> node4 = new Node<>(4,node3);
        node1.next = node4;
        System.out.println(checkCircle(node4));
    }
}

class Node<E> {
    E item;       // 当前元素的值
    Node<E> next; // 指向下一个元素

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

两个有序的链表合并

public class Test {
    // 单链表遍历
    public static void ergodic(Node curr){
        while(curr != null){
            System.out.print(curr.item);
            curr = curr.next;
        }
        System.out.println();
    }
    // 有序链表合并 Leetcode 21
    public static Node mergeTwoLists(Node<Integer> l1, Node<Integer> l2) {
        // 利用哨兵结点简化实现难度
        Node<Integer> soilder = new Node<>(0,null);
        // 初始化当前节点
        Node<Integer> curr = soilder;
        // 只要有一个链表遍历结束，另一个链表的剩余节点都将大于新链表
        while(l1 != null && l2 != null){
            // 将较小值 作为 当前节点 的 后节点
            if(l1.item < l2.item){
                curr.next = l1;
                // 更新 l1 节点
                l1 = l1.next;
            }else{
                curr.next = l2;
                l2 = l2.next;
            }
            // 更新当前节点
            curr = curr.next;
        }
        // 将 未遍历完 的 链表 直接 放到 新链表 尾部
        if(l1 != null) curr.next = l1;
        if(l2 != null) curr.next = l2;
        // 返回 不含 哨兵节点 的 链表
        return soilder.next;
    }
    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(7,null);
        Node<Integer> node2 = new Node<>(5,node1);
        Node<Integer> node3 = new Node<>(3,node2);
        Node<Integer> node4 = new Node<>(1,node3);
        Node<Integer> node5 = new Node<>(8,null);
        Node<Integer> node6 = new Node<>(6,node5);
        Node<Integer> node7 = new Node<>(4,node6);
        Node<Integer> node8 = new Node<>(2,node7);
        ergodic(mergeTwoLists(node4,node8));
    }
}

class Node<E> {
    E item;       // 当前元素的值
    Node<E> next; // 指向下一个元素

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

删除链表倒数第 n 个结点

public class Test {
    // 删除倒数第K个结点
    public static Node deleteLastKth(Node list, int k) {
        Node fast = list;
        int i = 1;
        while (fast != null && i < k) {
            fast = fast.next;
            ++i;
        }

        if (fast == null) return list;

        Node slow = list, prev = null;

        while (fast.next != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }

        if (prev == null) {
            list = list.next;
        } else {
            prev.next = prev.next.next;
        }
        return list;
    }
    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(1,null);
        Node<Integer> node2 = new Node<>(2,node1);
        Node<Integer> node3 = new Node<>(3,node2);
        Node<Integer> node4 = new Node<>(4,node3);
        Node<Integer> node5 = new Node<>(5,node4);
        Node<Integer> node6 = new Node<>(6,node5);
        System.out.println(deleteLastKth(node6,5).next.item);
    }
}

class Node<E> {
    E item;       // 当前元素的值
    Node<E> next; // 指向下一个元素

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

求链表的中间结点

public class Test {
    // 求中间结点
    public static Node findMiddleNode(Node list) {
        if(list == null) return null;
        Node fast =list, slow = list;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(1,null);
        Node<Integer> node2 = new Node<>(2,node1);
        Node<Integer> node3 = new Node<>(3,node2);
        Node<Integer> node4 = new Node<>(4,node3);
        Node<Integer> node5 = new Node<>(5,node4);
        Node<Integer> node6 = new Node<>(6,node5);
        System.out.println(findMiddleNode(node6).item);
    }
}

class Node<E> {
    E item;       // 当前元素的值
    Node<E> next; // 指向下一个元素

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

这篇关于单链表算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！