输入一个链表，反转链表后，输出新链表的表头(Java)

飞熊 • 2023年8月10日上午11:53 • 技术随笔 • 阅读 228

今天在牛客网上做了一个算法题，不知道是不是一孕傻三年的原因，竟然被一道难度为简单的算法题难住了。我觉得我可能不是做算法的这块料儿，还是老老实实的做java吧。

言归正传，我研究了半天，一定要记录一下：

题目：

说一下这个的解题思路：

刚开始我以为这个ListNode是个类似于java的集合类，我当即就想到了lamda表达式反转字符串。马上在右侧奋笔疾书，发现这个ListNode没有lamda方法。于是我觉得我想多了，这是个算法题怎么可能考察lamda表达式，傻帽儿。

我看了一下左边，原来有个说明：“说明：本题目包含复杂数据结构ListNode，点此查看相关信息”，我点进去看了一下，是这个样子的：

我转化成了java的类，大致明白了是个什么结构：

思路：当前的head的结构如上面右图所示。定义一个nextNode用来存放head的next的对象，定义一个用来存放反转之后对象的实体currentNode。反着来，从头获取head的每个节点，之后再将head的next设置成上个节点，指导head为空为止。代码如下：


    @Test
    public void test1() {
        //初始化
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        ListNode result = reverse(node1);
        while (result != null) {
            logger.info("next=====>{}", result.getVal());
            result = result.next;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode nextNode = null;
        ListNode currentNode = null;
        while (head != null) {
            nextNode = head.next;//将head的下个节点付给next
            head.next = currentNode;//将当前节点设置为head的下个节点
            currentNode = head;//再将head节点赋值给current
            head = nextNode;//将next赋值给head，继续循环
        }
        return currentNode;
    }

打印结果：