力扣算法Java热门面试题反转链表，力扣算法学习之路

约定不等于承诺〃 2023-10-02 17:12 11阅读 0赞

剑指 Offer II 反转链表，也是同事遇到过的面试题，题目如下  
![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_20_color_FFFFFF_t_70_g_se_x_16][]

看上图右侧的对象定义，链表的数据结构就很清晰了，一个节点对象，里面有一个 next 节点指向下一个节点对象。  
这个类似于 for 循环输出一个list ，只不过不采用 i++ 的方式而是 i-- 这种。

**以下代码思路讲解，  
比如链表 1>2>3>4>5 , 当前节点是 1>2>3>4>5 , 前节点 和 后节点 都是null ，  
第一次循环： 下一个节点 2>3>4>5 ，给当前节点的下一个节点赋值为前节点，也就是null (也就是1后面不再挂2>3>4>5） , 前节点等于当前节点（也就是 1），当前节点等于下一个节点 （2>3>4>5）  
第二次循环： 下一个节点 3>4>5 ，给当前节点的下一个节点赋值为前节点 (当前节点是2，前节点是1，当前节点就是 2>1) , 前节点等于当前节点（也就是 2>1），当前节点等于下一个节点 （3>4>5）  
第三次循环： 下一个节点 4>5 ，给当前节点的下一个节点赋值为前节点 (当前节点是3，前节点是2>1，当前节点就是 3>2>1) , 前节点等于当前节点（也就是 3>2>1），当前节点等于下一个节点 （4>5）**

以此类推，大白话的思路先取1出来，再取2出来，把1挂在2后面，再把3取出来，把2挂在3后面

package com.example.demo.test;
    
    /**
     * @author qiankun.hu
     * @version 1.0.0
     * @createTime 2021年12月03日 15:28:00
     * @Description 反转链表
     */
    public class Solution {
    
        public static void main(String[] args) {
            ListNode node5 = new ListNode(5,null);
            ListNode node4 = new ListNode(4,node5);
            ListNode node3 = new ListNode(3,node4);
            ListNode node2 = new ListNode(2,node3);
            ListNode node1 = new ListNode(1,node2);
    
            ListNode node = reverseList(node1);
        }
    
        /**
         * 反转链表
         * @param head
         * @return
         */
        public static ListNode reverseList(ListNode head) {
            //单链表为空或只有一个节点，直接返回原单链表
            if (head == null){
                return head;
            }
            //前一个节点指针
            ListNode preNode = null;
            //当前节点指针
            ListNode curNode = head;
            //下一个节点指针
            ListNode nextNode = null;
    
            while (curNode != null){
                nextNode = curNode.next;//nextNode 指向下一个节点
                curNode.next = preNode;//将当前节点next域指向前一个节点
                preNode = curNode;//preNode 指针向后移动
                curNode = nextNode;//curNode指针向后移动
            }
            return preNode;
        }
    
    
        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; }
        }
    
    }

解题方法来自力扣官网

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/98512e62e20f421cac3a5bb2ae1d4e1b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k,size_20,color_FFFFFF,t_70,g_se,x_16