Reverse Linked List

Reverse a singly linked list is a simple problem. Iterative and recursive solutions are given below. Note in the recursively solutions we persist a pointer to head.next before calling the function on next node as after reverse the list with head.next as head, head.next will become tail in the partial list. So we can always return new head for the list without losing the pointer to the tail.

Iterasive solution:

/**
 * 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 preHead = new ListNode(0); // we need not a stack to save nodes
        while (head != null) {
            ListNode next = head.next;
            head.next = preHead.next;
            preHead.next = head;
            head = next;
        }
        return preHead.next;
    }
}

Recursive solution:

/**
 * 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) return head;
        if (head.next == null) return head;

        ListNode next = head.next;
        ListNode newHead = reverseList(next);
        head.next = null;
        next.next = head;
        return newHead;
    }
}