206 Reverse Linked List

Reverse a singly linked list.

Example：

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Note：

A linked list can be reversed either iteratively or recursively. Could you implement both?

解释下题目：

简单的对一个链表进行reverse操作

1. 往头部插入

实际耗时：0ms

public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode fakeHead = new ListNode(0);
    fakeHead.next = null;
    ListNode tmp;
    while (cur != null) {
        tmp = cur;
        cur = cur.next;
        tmp.next = fakeHead.next;
        fakeHead.next = tmp;
    }
    return fakeHead.next;
}

  思路就是对于每一个节点，反向插入到一个新的链表中。

时间复杂度O(n)

空间复杂度O(1)

2. 递归方法

实际耗时：0ms

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

  思路递归理解起来其实有点困难，假设有1->2->3->4->5->6这么一个链表，然后目前现在的3，假设算法是正确的，那3之后的应该已经逆序完成了，也就是局部应该已经变成了1->2->3->4<-5<-6 那么此时应该让3的next的next指向3自己，也就是把3到4的箭头反个头，之后再让3这个指向Null（因为是递归）。实在理解不了就用第一种吧，第一种不仅好理解而且省空间。

时间复杂度O(n)

空间复杂度O(n)