【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;
        }
    }
}