leetcode 206： 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
Related Topics
递归
链表
思路1：使用头插法
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode();
ListNode p = head;
while(p != null){
ListNode temp = p.next;
//头插法
p.next = newHead.next;
newHead.next = p;
p = temp;
}
return newHead.next;
}
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.1 MB,击败了77.29% 的Java用户思路2 ：递归
/**
举例说明：5->4->3->2->1
最后一次递归时，当head等于2时，调用reverseList(1)返回1
通过head.next.next使1->2 此时 5->4->3->2-> <-1
通过head.next = null 此时 5->4-3->2<-1
以此类推
*/
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next); //每一次返回链表的头节点
head.next.next = head;
head.next = null;
return newHead;
}
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.2 MB,击败了40.86% 的Java用户版权声明：本文为yingmu__原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。