[2018-Interview] Reverse Linked List

Original question: https://leetcode.com/problems/reverse-linked-list/description/


My answer:

Iterative and recursive: too slow. Please check out the better solution below.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
           // Solution 1
        // if (head == null || head.next == null) {
        //     return head;
        // }
//         ListNode nextHead = reverseList(head.next);

//         ListNode endNode = nextHead;

//         while (endNode.next != null) {
//             endNode = endNode.next;
//         }
//         head.next = null;
//         endNode.next = head;
//         return nextHead;
        // Solution 2
        if (head == null || head.next == null) {
            return head;
        }
        LinkedList<ListNode> list = new LinkedList<ListNode>();
        ListNode current = head;
        while(current != null) {
            list.addLast(current);
            current = current.next;
        }
        while (!list.isEmpty() && list.size() != 1) {
            ListNode firstNode = list.removeFirst();
            ListNode lastNode = list.removeLast();
            int temp = firstNode.val;
            firstNode.val = lastNode.val;
            lastNode.val = temp;
        }
        return head;
    }
}

Better solution:

1. Iterative: move the next node of HEAD to be the one right after dummy node, until HEAD is the last one

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = head;
        while (cur->next) {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = dummy->next;
            dummy->next = tmp;
        }
        return dummy->next;
    }
};

2. Recursive:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *p = head;
        head = reverseList(p->next);
        // after above reversing, p->next is already the end node,
        // below steps move p to the end
        p->next->next = p;
        p->next = NULL;
        return head;
    }
};