Reverse Linked List

Reverse a singly linked list.

click to show more hints.

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

递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

基本递归

代码

public class Solution {        ListNode newHead;        public ListNode reverseList(ListNode head) {        reverse(head);        return newHead;    }        private ListNode reverse(ListNode n){        if( n == null || n.next == null){newHead = n;        } else {ListNode prev = reverseList(n.next);prev.next = n;        }        return n;    }}

迭代法

复杂度

时间 O(N) 空间 O(1)

思路

基本迭代

代码

public class Solution {    public ListNode reverseList(ListNode head) {        if(head == null || head.next == null) return head;        ListNode p1 = head;        ListNode p2 = p1.next;        while(p2 != null){ListNode tmp = p2.next;p2.next = p1;p1 = p2;p2 = tmp;        }        head.next = null;        return p1;    }}