Problem
Reverse a singly linked list.
Hint：
A linked list can be reversed either iteratively or recursively. Could you implement both?
My Solution
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode p = head, reverse = new ListNode(0);
if (p == null) {
return reverse.next;
}
ListNode q = new ListNode(p.val);
reverse = insertHead(reverse, q);
while (p.next != null) {
p = p.next;
q = new ListNode(p.val);
reverse = insertHead(reverse, q);
}
return reverse.next;
}
public ListNode insertHead(ListNode reverse, ListNode node) {
ListNode head = reverse;
if (head.next == null) {
head.next = node;
node.next = null;
} else {
node.next = head.next;
head.next = node;
}
return head;
}
}
Great 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;
}
