力扣每日一题2021/8/3

题目：206. 反转链表

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

难度：简单

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1. 递归
2. 迭代
3. 栈

解题代码

递归

/**
 * 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){
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        reverseList(dummy, dummy.next);
        return dummy.next;
    }
    public ListNode reverseList(ListNode dummy, ListNode node) {
        if (node.next == null){
            dummy.next.next = null;
            dummy.next = node;
            return node;
        }else {
            return reverseList(dummy, node.next).next = node;
        }
    }
}

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode before = null;
        ListNode p = head;
        while (p != null){
            ListNode q = p.next;
            p.next = before;
            before = p;
            p = q;
        }
        return before;
    }
}

栈

class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode(0, null);
        ListNode start = dummy;
        for (ListNode p = head; p != null; p = p.next){
            stack.push(p);
        }
        while (!stack.isEmpty()){
            start.next = stack.pop();
            start =start.next;
        }
        start.next = null;
        return dummy.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;
    }
}