206. Reverse Linked List

Problem

Difficulty: Easy
Tags: Linked List, Recursion

Intuition

This question would not be easy If I saw it for the first time, but I leared this algorithm in UW CS lecture, therefore I could solve this under 5 minuites.

Approach

just travel trough linked list and change the next value as you move one.

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(!head){
        return NULL;
    }
    struct ListNode* ans = head;
    struct ListNode* tmp;
    struct ListNode* prev = NULL;
    while(ans){
        tmp = ans->next;
        ans->next = prev;
        prev = ans;
        ans = tmp;
    }
    return prev;
}

Complexity

Time: $O(n)$
Space: $O(1)$

Thoughts

This would be one of the most common problem in Algorithm and data structure class.