反转链表

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。

样例 输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL

迭代

时间复杂度O(n)

class Solution { public ListNode reverseList(ListNode head) { if(head == null){ return null; } ListNode res = null; while(head != null){ if(res == null){ res = new ListNode(head.val); }else{ ListNode list1 = new ListNode(head.val); list1.next = res; res = list1; } head = head.next; } return res; } }

递归

时间复杂度O(n)

class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode node= reverseList(head.next); head.next.next=head; head.next=null; //每次递归都返回最后一个结点 return node; } }