206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Thoughts

• Pretty easy, simple as iterating through the list and building the list in reverse order

Solution

/**
 * 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) {
        ListNode cur = head;
        ListNode newList = null;
        while (cur != null) {
            if (newList == null) {
                newList = new ListNode(cur.val);
            } else {
                ListNode newNode = new ListNode(cur.val, newList);
                newList = newNode;
            }
            cur = cur.next;
        }
        return newList;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

Conclusion

Pretty simple, but its good to brush up on concepts I haven't used in a while. I honestly can't remember the last time I had to manipulate a linked list so this was a nice refresher on that. Definitely need to work on some of the more complex linked list topics though.