Skip to content

206 LeetCode Java: Reverse Linked List -Easy

Problem:

Reverse a singly linked list.

Thoughts:

Very simple and straight forward problem on pointer manipulation of linked list nodes.

Solutions:

Recursion version:

/**
* 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 fakeHead = new ListNode(-1);
        reverse(head, fakeHead);
        return fakeHead.next;
    }
    //reverse returns the tail of the reversed list
    private ListNode reverse(ListNode node, ListNode fakeHead){
        if (node == null)
            return fakeHead;
        else{
            ListNode tail = reverse(node.next, fakeHead);
            tail.next = node;
            node.next = null;
            return node;
        }
    }
}
Non-recursion version:

/**
* 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 fakeHead = new ListNode(-1);
        ListNode node = head;
        while (node != null){
            ListNode nodeNext = node.next;
            node.next = fakeHead.next;
            fakeHead.next = node;
            node = nodeNext;
        }
        return fakeHead.next;
    }
}