【LeetCode】 206. Reverse Linked List

Description

Reverse a singly linked list.

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

反轉一個單向的串列鏈結。

進階：
一個串列鏈結可以用迭代或是遞迴實作，你可以兩種都實作嗎？

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution

• 設三個點：前一個、現在、下一個。
• 每次Loop，把現在的next設為前一個，接著把三個點都往下移。重複至到尾巴(NULL)。
• 遞迴的比較想法困難，把點拆為兩個兩個一組，將後面的點的next往回設，將自己的點的next設為NULL。然後用遞迴從後面開始往回做。

Code

• Iteratively

/**
 * 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 || !head->next) return head;
        ListNode* next = head->next;
        ListNode* newHead = head;
        ListNode* pre = NULL;
        
        while(next)
        {
            pre = newHead;
            newHead = next;
            next = newHead->next;
            newHead->next = pre;
        }
        head->next = NULL;
        return newHead;
    }
};

• Recursively

/**
 * 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 || !head->next) return head;
        ListNode* n = head->next;
        n = reverseList(n);
        head->next->next = head;
        head->next = NULL;
        return n;
    }
};

tags: LeetCode C++