简单的算法：链表倒置问题

简单的算法：链表倒置问题

        单链表是我们经常使用也是比较简单的数据结构。单链表的倒置是面试中常会问到的问题，下面我来简单介绍一下如何解决链表倒置问题。

在实现倒置算法之前，我们需要明确一个概念：头插法与尾插法。

        头插法：头插法是链表的每一次数据插入都插在链表的第一个节点。头插法会使链表变成插入顺序的逆序，但头插法效率高，不需要遍历整个链表。过程如图所示：

        尾插法：尾插法是链表的每一次数据插入都插在链表的最后一个节点。尾插法需要每次都循环一次链表，找到最后一个节点，再进行插入。过程如图所示：

为了说明头插法与尾插法，我实现了一个简陋的单链表

public class linkList {

    private Node head = new Node();

    class Node {
        String value;
        Node next;
    }

    
    public void headInsert(String value) {
        Node node = new Node();
        node.value = value;
        node.next = head.next;
        head.next = node;
    }

    
    public void tailInsert(String value) {
        Node node = new Node();
        node.value = value;
        Node tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = node;
    }

    public String toString() {
        Node node = head.next;
        String mes = "";
        while (node != null) {
            mes = mes + "Node:" + node.value + "; ";
            node = node.next;
        }
        return mes;
    }
}

        测试代码

public class InversionTest {

    public static void main(String[] args) {

        System.out.println("========头插法输出==========");
        linkList headInsertList = new linkList();
        headInsertList.headInsert("1");
        headInsertList.headInsert("2");
        headInsertList.headInsert("3");
        headInsertList.headInsert("4");
        headInsertList.headInsert("5");
        System.out.println(headInsertList);

        System.out.println("========尾插法输出==========");
        linkList tailInsertList = new linkList();
        tailInsertList.tailInsert("1");
        tailInsertList.tailInsert("2");
        tailInsertList.tailInsert("3");
        tailInsertList.tailInsert("4");
        tailInsertList.tailInsert("5");
        System.out.println(tailInsertList);
    }
}

        结果

在普及完头插法与尾插后，我们言归正题。

        怎么才能将一个单向链表倒置呢，我的思路是利用头插法的特点，将每个获取的node节点删掉，使用头插法将节点重新插入到链表。

public void reversel() {
    // 获取第一个节点
    Node node = head.next;
    // 节点不为空并且下一个节点不为空
    while (node != null && node.next != null) {
        // 获取下一个节点的值
        String value = node.next.value;
        // 使用头插法插入下一个节点的值
        headInsert(value);
        // 将node的下一个节点删除
        node.next = node.next.next;
    }
}

        测试一下

public class InversionTest {

    public static void main(String[] args) {
        System.out.println("========原始链表==========");
        linkList originalList = new linkList();
        originalList.headInsert("1");
        originalList.headInsert("2");
        originalList.headInsert("3");
        originalList.headInsert("4");
        originalList.headInsert("5");
        System.out.println(originalList);

        System.out.println("========倒置链表==========");
        originalList.reversel();
        System.out.println(originalList);
    }
}

        结果

这样，我们就解决了这个问题，如果您有更好的思路，欢迎在评论区留言告诉我一下。 感谢大家的惠读！