題目

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)
            return head;

        ListNode root = null;
        while (head != null)
        {
            ListNode next = head.next;
            head.next = root;
            root = head;
            head = next; 
        }
        return root;
    }
}

結果

Runtime: 88 ms, faster than 97.87% of C# online submissions.

Memory Usage: 23.4 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)
[Day 19] 演算法刷題 LeetCode 206. Reverse Linked List (Easy) Part 1

昨天已經講了遞迴的解法，今天要來講 疊代 Iteration 解法

1. 宣告一個 ListNode root 當作新的 head
2. 使用 while 迴圈 判斷 LinkedList 裡是否還有 next
   • 宣告 ListNode next 記錄當下的 next node 是誰
   • next 改 串接 root
   • root 則改為已經串接好的 head
   • head 則改為原本的 next
3. 回傳已經反轉的 LinkedList

主要是邊找下一個 head node，邊將 head node 串接到新的 LinkedList root 前面，這樣就會是反轉的

示意圖

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

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