206. Reverse Linked List

題目：
Given the head of a singly linked list, reverse the list, and return the reversed list.
給定一個單向鏈結串列的頭節點 head，請反轉這個鏈結串列，並回傳反轉後的頭節點

範例：

• Example 1:
  Input: head = [1,2,3,4,5]
  Output: [5,4,3,2,1]

• Example 2:
  Input: head = [1,2]
  Output: [2,1]

• Example 3:
  Input: head = []
  Output: []

想法：
利用三指標

• prev：指向前一個節點（初始為 null）
• curr ：目前正在處理的節點
• next ：暫存 curr.next，避免鏈結斷掉

1 → 2 → 3 → 4 → 5 → null
prev curr next
null 1 2 ← 開始前
操作：
curr.next = prev ← 把箭頭反過來
prev = curr ← prev 往前走
curr = next ← curr 往前走

重複直到 curr 為 null！

程式碼：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;     //前一個節點，初始為null
	 ListNode curr = head;  //當前節點從head開始

	while (curr != null){
		ListNode next = curr.next; //暫存下一個節點
		curr.next = prev; //將當前節點的next指向前一個節點（反轉）
		prev = curr;  //prev 向前移動
		curr = next;  //curr 向前移動
   	 }
	return prev; //最後prev指向新的頭節點
}

實際操作：

原始：
head → 1 → 2 → 3 → 4 → 5 → null

STEP1

• curr = 1
• next = 2 (暫存 curr.next)
• curr.next = prev → 1.next = null
• prev = 1
• curr = 2

prev → 1 → null
curr → 2 → 3 → 4 → 5 → null

STEP2

• curr = 2
• next = 3
• curr.next = prev → 2.next = 1
• prev = 2
• curr = 3

prev → 2 → 1 → null
curr → 3 → 4 → 5 → null

STEP3

• curr = 3
• next = 4
• curr.next = prev → 3.next = 2
• prev = 3
• curr = 4

prev → 3 → 2 → 1 → null
curr → 4 → 5 → null

STEP4

• curr = 4
• next = 5
• curr.next = prev → 4.next = 3
• prev = 4
• curr = 5

prev → 4 → 3 → 2 → 1 → null
curr → 5 → null

STEP5

• curr = 5
• next = null
• curr.next = prev → 5.next = 4
• prev = 5
• curr = null → 迴圈結束

prev → 5 → 4 → 3 → 2 → 1 → null
curr = null

——＞5 → 4 → 3 → 2 → 1 → null