[Day 2] Leetcode 206. Reverse Linked List (C++)

前言

今天的题目一样是easy，不过我觉得很值得练习！题目在这边：206. Reverse Linked List，是在反转linked list。我认为对指标不熟的人可能会很头痛XD 那就趁机来补充一点指标的概念吧！我也是这阵子才好好地搞清楚其中的关系，之前都有点半写半背，过一阵子就忘记了，直到彻底理解了指标，这题对我而言才真的成为easy，不用去记做法就能做出来，哈哈。

ListNode class

在开始解题之前，我们不如顺便来看看题目在上面给定的ListNode的class，虽然它是struct，不过class跟struct的差异只有一个预设是private，一个是public而已。
这个ListNode里面有哪些成员呢？答案是：
1.val这个整数与
2.next这个指向ListNode型别的指标

剩下的部分都是这个class的constructor，constructor是用来确保ListNode这个类别可以被好好初始化，而写法就是会跟class本身同名、没有return type、有(可能是空的)参数列表与(可能是空的)函式本体。可以看到有三种建构子，代表说我们可以用ListNode()、ListNode(x)、ListNode(x, p)这几种方式来初始化它。
而至於後面的部分，我之前对於这个写法有点疑惑，想说一堆()(){}{}是在干嘛，其实这个写法是直接初始化的用法，ListNode() : val(0), next(nullptr) {}换种写法就是

ListNode(){
    val=0;
    next=nullptr;
}

代表说如果我们丢一个空的来建立ListNode这个物件，ListNode a = new ListNode();，那a的value就会是0，而next则是nullptr。但比起这种assignment的写法，建议还是用直接初始化的写法会更有效率。也许之後可以再找一天讨论建构子的部分XD 废话不多说还是先进题目好了。

想法

要怎麽进行反转呢？其实也有一种暴力作法，直接遍历纪录node value，存到vector里面，再建立n个node去串回去XD 但这就比较耗空间了，我们还是直接把题目给的linked list倒过来吧！
我们可以先思考我们每次需要纪录哪些东西。首先，需要有一个node指标是按顺序去走完整个list；还要有一个指标，去保存前一个node，让後面的node可以指回去；然後还要有一个指标担任去把现在的node指回前一个node的角色。所以，我们需要三个指标，题目已经提供了一个head，我们可以直接拿来用，那就再两个XD。
指向前一个node的指标我们叫它prev，因为倒过来，所以第一个prev应该是nullptr(reversed linked list的末尾)

ListNode* prev = nullptr;

然後要负责指回去的我们叫它cur好了，从第一个开始要来反转。

ListNode* cur = head;

前置作业两个指标初始化完毕，我们来遍历整个linked list吧，要判断是否抵达结尾，我们可以看是否已经指向了nullptr

while(nullptr!=head){
/*reverse*/
}

那中间的reverse要如何实做呢？
首先，我们要先让head走到下一个位置，再来让cur指回prev，
这个顺序很重要，不然现在cur跟head是指向同一个node，如果先让cur指标提领(dereference)出来指向prev，head的next也会变prev唷XD 就走不下去了。

head = head->next; // 改变head指向的方向，head现在指向原来的next的ListNode

head已经抵达下一个node，我们就可以实作前面反转的部分了

cur-> next = prev; // 注意，这里不是!!改变cur的指向，而是"提领"cur指标指向的东西，然後赋值唷!!因为cur->X会=(*cur.X)，前面*cur代表的是把cur指标指向的地方提领出来!!所以这个指标把原来那个node的next改掉了!!

接下来就让大家keep going，下一轮的prev就是现在的cur；而下一轮的cur则是现在的head

prev = cur;
cur = head;

就这样。没错，这样就结束了！
完整程序码如下：

/**
 * 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) {
        // head to go through the list in order
        // 'prev' pointer keep the previous node
        ListNode* prev = nullptr;
        // cur pointer to redirect the node
        ListNode* cur = head;
        
        // go through list till the head become new pointer
        while(nullptr!=head){
            // head step to the next
            head = head->next;
            // cur node point to the prev
            cur->next = prev;
            // prev points to cur
            prev = cur;
            // update cur to the next node
            cur = head;
        }
        return prev;
    }
};

最後要return的为什麽是prev呢？因为可以看到最後一轮cur跟head都变成nullptr了！而当下的prev就是前一轮反转後的cur罗！

结语

今天不知不觉打比较多，接下来不一定要跟着9月challenge，加一些经典的题目好了XD