Epoch

題目

  Reverse a singly linked list

Hint

  A linked list can be reversed either iteratively or recursively. Could you implement both?

想法

  Interative

    利用三個 node，p 一直指向下一個 node，q 一直跟著 p，r 一直跟著 q；p 移動後，q 跟上，並將 next 指向跟著自己的 r，即反轉。最後別忘記 assign head = q。

code

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *p = head;
    struct ListNode *q = 0;
    while(p) {
        struct ListNode *r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    return p;
}

  recursive

    主要用兩個 node 來記錄資訊，第一個 node 稱為 p，第二個 node 稱為 q

p 不斷的前進，q 則是跟著 p，p 前進後，q 會將 next assign null

直到 p 走到盡頭，開始將 p->next 指向剛剛跟著他的 q，一層一層走回去。

code

struct ListNode* reverseList(struct ListNode* head) {
    if (!head || !head->next) return head;
    else {
            struct ListNode *q = head->next;
            head->next = NULL;
            struct ListNode *rest = reverseList(q);
            q->next = head;
            return rest;
        
    }
}