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

刺骨的言语ヽ痛彻心扉 2023-10-05 15:59 5阅读 0赞

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

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

题目：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70][]

说一下这个的解题思路：

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 3][]

思路：当前的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;
        }

打印结果：

![20201216201214398.png][]

过程我用excel表示一下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 4][]

实在不懂的话，可以用debugger打一下。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201216192209347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.nowcoder.net/n/954373f213e14eeab0a69ed0e9ef1b6e
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020121619253867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020121619265266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020121619404482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[20201216201214398.png]: https://img-blog.csdnimg.cn/20201216201214398.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201216200748138.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70