Question
Reverse a singly linked list.
Solution 1 -- Iterative
Remember to set head.next = null or it will report "memory limit exceeds" error.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode current = head, prev = head, post = head;
if (current == null || current.next == null)
return current;
current = current.next;
head.next = null;
while (current.next != null) {
post = current.next;
current.next = prev;
prev = current;
current = post;
}
current.next = prev;
return current;
}
}
Solution 2 -- Recursive
We can also use recursion to solve this problem.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode second = head.next;
head.next = null;
ListNode newHead = reverseList(second);
second.next = head;
return newHead;
}
}