1 package 链表操作.q206_反转链表.f1;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
/**
* 遍历直接反向修改next指针 o(n)
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode temp = head;
while (temp != null) {
ListNode t = temp.next;
temp.next = pre;
pre = temp;
temp = t;
}
return pre;
}
}
2 package 链表操作.q206_反转链表.f2;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
/**
* 递归法 o(n)
*/
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;
}
}