Given the head of a singly linked list, reverse the list, and return the reversed list.
Examples
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2:
Input: head = [1,2] Output: [2,1]
Input: head = [] Output: []
Constraints:
The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Java Solution
Iterative
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)return head;
ListNode current = head;
ListNode next = current.next;
current.next = null;
while(current != null && next != null) {
ListNode temp = next.next;
next.next = current;
current = next;
next = temp;
}
return current;
}
}
Recursive
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)return head;
ListNode next = head.next;
head.next = null;
ListNode temp = reverseList(next);
next.next = head;
return temp;
}
}