🌗 剑指 Offer 24. 反转链表

难度: 🌗

问题描述

---

解法 1 - 迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 思路：
        // 迭代
        if(head == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

---

输出 1

---

解法 2 - 递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 思路：
        // 递归
        return mySol(null, head);
    }

    private ListNode mySol(ListNode pre, ListNode cur) {
        // 递归终止条件
        if(cur == null) {
            return pre;
        }
        // cur != null
        ListNode next = cur.next;
        cur.next = pre;
        return mySol(cur, next);
    }
}

---

输出 2