206.Reverse Linked List

Solution 1: Using Stack

Don't forget to set tmpNode.next = null after the while loop, or ill get a TLE

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        Stack<ListNode> stack = new Stack();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode preHead = new ListNode(0);
        ListNode tmpNode = preHead;
        while(!stack.empty()){
            tmpNode.next = stack.pop();
            tmpNode = tmpNode.next;
        }
        tmpNode.next = null;
        return preHead.next;
    }
}

Solution 2-Iterative O(n)

Assume that we have linked list1 → 2 → 3 → Ø, we would like to change it toØ ← 1 ← 2 ← 3.

While you are traversing the list, change the current node's next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null){
            ListNode tmpNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmpNext;
        }
        return prev;
    }
}

Solution 3-Recursive-On

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