206 - Reverse Linked List

#easy

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

KEY POINT: 注意一開始頭尾巴要接NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if ( head == NULL ) return NULL;
        ListNode * it_node = head;
        ListNode * n_node = NULL;
        if ( head -> next == NULL ) return head;
        else n_node = head -> next;
        ListNode * nn_node = NULL;
        while ( it_node != NULL )  {
            if ( n_node -> next != NULL ) {
                nn_node = n_node -> next;
                n_node -> next = it_node;
                it_node = n_node; 
                n_node = nn_node;
            }
            else {
                n_node -> next = it_node;
                // 注意一開始頭尾巴要接NULL
                head -> next = NULL;
                head = n_node;
                break;
            }

        }   

        return head;
    }
};

it_node -> n_node -> nn_node

• it_node -> n_node -> nn_node

**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode * pre = NULL;
    ListNode * traversal( ListNode * head, ListNode * pre ) {
        if ( head == NULL ) return pre; 
        ListNode * temp = head -> next;
        head -> next = pre;
        return traversal( temp, head );
    }

    ListNode* reverseList(ListNode* head) {
        // if ( head == NULL ) return NULL;
        // stack<ListNode*> st;
        // while( head != NULL ) {
        //     st.push( head );
        //     head = head -> next;
        // }

        // head = st.top();
        // ListNode * node = head;
        // st.pop();
        // while( !st.empty() ) {
        //     ListNode * node_next = st.top();
        //     st.pop();
        //     node -> next = node_next;
        //     node_next -> next = NULL;
        //     node = node_next;
        // }

        // return head;
        return traversal( head, NULL );
    }
};


// class Solution {
// public:
//     ListNode* reverseList(ListNode* head) {
//         ListNode* temp; // 保存cur的下一個節點
//         ListNode* cur = head;
//         ListNode* pre = NULL;
//         while(cur) {
//             temp = cur->next;  // 保存一下 cur的下一個節點，因為接下來要改變cur->next
//             cur->next = pre; // 翻轉操作
//             // 更新pre 和 cur指針
//             pre = cur;
//             cur = temp;
//         }
//         return pre;
//     }
// };

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

    return prev;
}