LeetCode：206. 反转链表

问题链接

206. 反转链表

问题描述

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

示例

解题思路

这道题简单，但是比较考验链表、指针的基本功。

1. 递推
   遍历链表，将当前节点的指针改为指向前一个节点（没有前节点，就指向null）。
2. 递归
   实质就是从链表的底部开始，更改“箭头”方向。

代码示例（JAVA）

递推

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newNode = null;

        ListNode cur = head;
        while (cur != null) {
            // 先把下个节点存一下
            ListNode next = cur.next;
            // 将当前节点放到链表
            cur.next = newNode;
            newNode = cur;
            // 移动cur到下一个节点
            cur = next;
        }
        return newNode;
    }
}

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 找反转后的链表头
        ListNode newHead = reverseList(head.next);
        // 当前节点“箭头”反转
        head.next.next = head;
        head.next = null;

        return newHead;
    }
}