反转链表

* 反转一个单链表。
* 输入: 1->2->3->4->5
* 输出: 5->4->3->2->1

package com.apesblog.day_20221211;

/**
* @author ZhangYuShun
* @since 2022/12/11
* <p>
* 反转一个单链表。
* 输入: 1->2->3->4->5
* 输出: 5->4->3->2->1
*/

public class ReverseList {

   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);
       System.out.println(node1);

       ListNode iterate = iterate(node1);
       System.out.println(iterate);

       ListNode recursion = recursion(iterate);
       System.out.println(recursion);
   }

   /**
    * 递归
    */
   private static ListNode recursion(ListNode curr) {

       if (curr.next == null) {
           return curr;
       }
       ListNode newHead = recursion(curr.next);
       curr.next.next = curr;
       curr.next = null;
       return newHead;

   }

   /**
    * 三个指针
    */
   private static ListNode iterate(ListNode node1) {
       if (node1 == null) {
           return null;
       }
       ListNode pre = null;
       ListNode curr = node1;
       ListNode next = null;
       while (curr != null) {
           next = curr.next;
           curr.next = pre;
           pre = curr;
           curr = next;
       }
       return pre;
   }

   static class ListNode {
       int val;
       ListNode next;

       public ListNode(int val, ListNode next) {
           this.val = val;
           this.next = next;
       }

       @Override
       public String toString() {
           StringBuilder sb = new StringBuilder(String.valueOf(val));
           ListNode next = this.next;
           while (next != null) {
               sb.append(next.val);
               next = next.next;
           }
           return sb.toString();
       }
   }
}