題目

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

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

Follow up:

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

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */  
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null ||head.next == null){
            return head;
        }
        
        ListNode root = ReverseList(head.next);
        
        head.next.next = head;
        head.next = null;
        return root;
    }
}

結果

Runtime: 84 ms, faster than 99.64% of C# online submissions.

Memory Usage: 23.9 MB, less than 8.0% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

LinkedList 小回顧 ↓
[Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy)
[Day 15] 演算法刷題 LeetCode 141. Linked List Cycle (Easy)
[Day 16] 演算法刷題 LeetCode 142. Linked List Cycle II (Medium)
[Day 17] 演算法刷題 LeetCode 2. Add Two Numbers (Medium)
[Day 18] 演算法刷題 LeetCode 234. Palindrome Linked List (Easy)

這題題目很明確，就是要讓使用者輸入的 linkedList 反轉。
方式有兩種，一種是 遞迴 Recursion，一種是 疊代 Iteration，這邊則是遞迴解法，明天才會講解疊代解法唷！

1. 判斷 head 或 head.next 是否為 null，若 是 則回傳 head
2. 宣告 ListNode root 使用遞迴去找出反轉後的 head，就是根據 1. 去判斷，若找到 root 後開始回傳
3. head.next.next 改串接為 head
4. head.next 則指向 null 斷開 cycle 的情況
5. 回傳已經反轉的 LinkedList

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉