数据结构之链表：彻底搞懂单链表反转

1、代码实现

ListNode是一个链表类，维护了头节点、节点数，内部类实现Node节点类。

public class ListNode<Integer> {
          
   
    //头部节点
    Node<Integer> head;
    //节点数
    int size=0;
    public static class Node<T> {
          
   
        //data值
        T vaule;
        //指向下一个节点
        Node<T> next;
        //构造方法
        public Node(T vaule, Node<T> next) {
          
   
            this.vaule = vaule;
            this.next = next;
        }
         @Override
        public String toString() {
          
   
            return "Node{" +
                    "vaule=" + vaule +
                    ", next=" + next +
                    };
        }
    }
    /**
     * 链表添加方法
     * @param data
     */
    public void add(Integer data){
          
   

        if(head==null){
          
   
            head= new Node<>(data, null);
            size++;
        }else{
          
   
            Node<Integer> temp=head;
            while(temp.next!=null){
          
   
                temp=temp.next;
            }
            temp.next= new Node<>(data, null);
            size++;
        }
    }
    /**
     * 反转链表
     */
    public Node reverseNode() {
          
   
        Node pre = null;
        Node next;
        
        while (head != null) {
          
   
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre; 
    }
}

2、图文解析

重点解析：

next = head.next;
    head.next = pre;
    pre = head;
    head = next;

链表的反转关键就在于这四行代码，一步步解析。

这是反转前链表。 这是反转后链表。 第一步： next = head.next;即用next保存头节点的下一个节点（节点2）。 第二步： head.next = pre;将pre（null）赋值给head.next。 第三步： pre = head;将head赋值给pre，即head指向节点1，将节点1设置为pre节点。 第四步： head = next;将next赋值给head,即head指向节点2，将节点2设置为头节点。 一次循环结束，此时链表被分成2段。继续下一轮循环： 第一步： next = head.next;即用next保存头节点的下一个节点（节点3）。 第二步： head.next = pre;将pre（节点1）赋值给head.next。即节点2的后继为节点1，完成一次反转。 第三步： pre = head;将head赋值给pre，即head指向节点2，将节点2设置为pre节点。 第四步： head = next;将next赋值给head,即head指向节点3，将节点3设置为头节点。 继续第三轮、第四轮循环，链表反转完成，我们看到第二步是一次关键的反转操作，在第一次循环中，head.next = pre;将pre（null）赋值给head.next。相当于将尾节点tail完成反转。

3、测试验证

public class ListNodeTest {
          
   
   public static void main(String[] args) {
          
   
     ListNode<Integer> listNode = new ListNode<>();
     listNode.add(1);
     listNode.add(2);
     listNode.add(3);
     listNode.add(4);

     System.out.println(listNode.reverseNode());
 }
}

运行结果：