题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路

递归和遍历两种做法：

  1. 顺序遍历，定义 now，pre，aft 三个指针，分别指向当前节点，前一个节点，下一个节点。遍历的时候反转链表即可。让当前节点从 pre->now->next1->next2 变成 pre<-now next1->next2，pre 节点让链表反向，aft 节点记录 next1 节点，不然链表就断了。
  2. 递归到链表尾部，然后依次反转整个链表。细致一点的图可以看这

image.png

代码实现

  1. import java.util.Scanner;
  3. public class Problem15 {
  4.     public class ListNode {
  5.         int val;
  6.         ListNode next;
  8.         ListNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  13.     public static ListNode ReverseList(ListNode head) {
  14.         ListNode now = head;
  15.         ListNode pre = null;
  16.         ListNode aft = head.next;
  17.         while (now != null) {
  18.             aft = now.next;
  19.             now.next = pre;
  20.             pre = now;
  21.             now = aft;
  22.         }
  23.         return pre;
  24.     }
  26.     public static ListNode ReverseList1(ListNode head) {
  27.         if (head == null || head.next == null)
  28.             return head;
  29.         ListNode reverseHead = ReverseList(head.next);
  30.         head.next.next = head;
  31.         head.next = null;
  32.         return reverseHead;
  33.     }
  35.     public static void main(String[] args) {
  36.         Scanner cin = new Scanner(System.in);
  37.     }
  38. }