206. Reverse Linked List

Reverse a singly linked list.


解法 :
      其實資料結構的課本上就有，但是實在懶得再去翻書了，所以在這邊註記一下

      假設Linked-List是長這樣
     
      1 -> 2 -> 3 -> 4 -> 5

      那麼在這邊先給定三個變數，分別是previous(上一個)，current(當前的)，以及下一個(later)
      一開始的初始值給定
      previous = nullptr
      current當然就是 1
      later 就是 2

      接下來一直進行以下的動作
      回合1
      1.current->next改成指向previous而不是指向2
        nullptr <- 1  2 -> 3 -> 4 -> 5
           p       c  l

      2.previous設為1
        nullptr <- 1 2 -> 3 -> 4 -> 5
                       c l
                       p
      3.將current設為2
        nullptr <- 1 2 -> 3 -> 4 -> 5
                       p c
                       l
      4.將last設為3
        nullptr <- 1 2 -> 3 -> 4 -> 5
                        p c    l
      接下來的回合完全一樣只是起始點變了

程式碼                 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if(head == nullptr)
            return head;
        
        ListNode *previous = nullptr,
                 *current = head,
                 *later = head->next;
        
        while(later != nullptr)
        {
            current->next = previous;
            previous = current;
            current = later;
            later = later->next;
        }
        //current最後的next還要再重新指回上一個才可以接起來
        current->next = previous;
        
        return current;
    }
};