【Hot100】LeetCode—206. 反转链表

---

• 原题连接：206. 反转链表

---

1- 思路

递归法

• 递归三部曲
  • ①终止条件：遇到 head ==null || head.next==null 的时候
  • ②递归逻辑：定义 cur ，cur 执行递归逻辑，也就是调用 当前reverse(cur.next)
    • head.next.next = head;
    • head.next = null;

---

2- 实现

⭐206. 反转链表——题解思路

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next==null){return head;}// 递归ListNode cur = reverseList(head.next);head.next.next = head;head.next = null;return cur;}
}

---

3- ACM 实现

public class reverseList {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode reverseList(ListNode head){if(head == null|| head.next == null){return head;}ListNode cur = reverseList(head.next);head.next.next = head;head.next = null;return cur;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表长度");int n = sc.nextInt();ListNode head = null,tail=null;for(int i = 0 ; i < n;i++){ListNode nowNode  = new ListNode(sc.nextInt());if(head==null){head = nowNode;tail = nowNode;}else{tail.next = nowNode;tail = nowNode;}}ListNode forRes = reverseList(head);while(forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}
}