0206 - Reverse Linked List

0206 - Reverse Linked List

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;

    }
}