链表｜ Leetcode 206

Leetcode 分类刷题 —— 链表类（Linked List）

1、题目

Leetcode 206. Reverse Linked List

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

2、思路

迭代法：从前往后遍历，将当前节点指向它前面的节点
递归法：递归调用，使得下一个节点指向前一个节点

3、Java 代码

 public class LeetCode_206_Solution {
    /**
     * 迭代法
     * 1 -> 2 -> 3 -> 4 -> null
     * null <- 1 <- 2 <- 3 <- 4
     */
    public static ListNode reverseListIterative(ListNode head) {
        //前指针节点、当前指针节点
        ListNode prev = null;
        ListNode curr = head;
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            //临时节点，暂存当前节点的下一节点，用于后移
            ListNode nextTemp = curr.next;
            //将当前节点指向它前面的节点
            curr.next = prev;
            //前指针后移
            prev = curr;
            //当前指针后移
            curr = nextTemp;
        }
        return prev;
    }


    /**
     * 递归法
     * 1 -> 2 -> 3 -> 4 -> null
     * 1 -> 2 -> 3 <- 4
     * 1 -> 2 <- 3 <- 4
     */
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //前指针节点head是3；当前指针节点cur是4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

}

参考文章：
https://leetcode.cn/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/