LeetCode 206. 反转链表

206. 反转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

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

---

• 1.暴力解法

思路：
遍历要反转的链表，将每个元素依次插入一个新的链表的最前面即可完成反转

public static class ListNode {

        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        //用于测试用例
        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }

    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = newHead;
            newHead = node;
            head = head.next;
        }
        return newHead;
    } 

复杂度分析：
时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n), 每次都要重新开辟空间去新建节点

• 2.迭代法

思路：
将当前节点的next指向前一个元素即可

image.png

public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode p = cur.next;
            cur.next = prev;
            prev = cur;
            cur = p;
        }
        return prev;
    }

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

• 3.递归法

思路：
相当于每次先反转头节点之后的节点，反转完成之后在将头节点插入最后即可

image.png

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

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)，由于使用了递归，将会使用隐式栈空间，递归深度可能会达到n层

• 测试用例

public static void main(String[] args) {
        int[] nums = new int[] {1, 2, 3};
        ListNode head = new ListNode(nums);
        System.out.println(head);
        System.out.println("反转后的链表" + reverseList(head));
    }

• 结果

1->2->3->4->5->NULL
反转后的链表5->4->3->2->1->NULL

---

• 源码

• 我会随时更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github