AcWing 35. 反转链表
原题链接
简单
Java代码
方法一:投机法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
int n = 0;
for(ListNode p = head; p != null; p = p.next){
n ++;
}
int[] d = new int[n];
for(ListNode p = head; p != null; p = p.next){
d[ --n] = p.val;
}
int idx = 0;
for(ListNode p = head; p != null; p = p.next){
p.val = d[idx ++];
}
return head;
}
}
方法二:迭代法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode p = head, q = head.next;
while(q != null){
ListNode t = q.next;
q.next = p;
p = q;
q = t;
}
head.next = null;
return p;
}
}
方法三:递归法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode new_node = reverseList(head.next);
head.next.next = head;
head.next = null;
return new_node;
}
}