题目
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例
方法一:迭代
比如需要链表为 1->2->3->4->null ,反转后就是null <--1 <-- 2 <-- 3 <-- 4
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
方法二:递归
class Solution {
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.执行递归代码当head = 3时,p调用递归,head.next=4,因为4下一个为null,所以返回的是head,也就是3,递归就到头了,接着就是执行head.next.next = head,也就是4的下一个节点为3,这就使得3 -- > 4 变成了 3 <-- 4