LeetCode 206 Reverse Linked List

递归实现

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {
    // recursivelypublic ListNode reverseList(ListNode head) {
    if(head == null || head.next == null)return head;ListNode t = reverseList(head.next);head.next.next = head;head.next = null;return t;}
}

迭代实现

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {
    // iterativelypublic ListNode reverseList(ListNode head) {
    ListNode prev = null;while(head != null) {
    ListNode next = head.next;head.next = prev;prev = head;head = next;if(next != null)next = next.next;}return prev;}
}

复杂度

时间复杂度O(n)
空间复杂度O(n)