鏈表創建（C#）

在C#中，鏈表可以通過自定義節點類實現。每個節點包含數據域和指向下一個節點的引用。

public class ListNode {public int val;public ListNode next;public ListNode(int val=0, ListNode next=null) {this.val = val;this.next = next;}
}// 創建鏈表示例
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

三指針反轉鏈表

三指針法通過維護前驅（prev）、當前（curr）和后繼（next）三個指針實現鏈表反轉，時間復雜度O(n)，空間復雜度O(1)。

public ListNode ReverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next; // 保存后繼節點curr.next = prev;         // 反轉指針方向prev = curr;              // 前驅指針后移curr = next;              // 當前指針后移}return prev; // 新頭節點
}

關鍵步驟解析

初始化時prev為null，curr指向頭節點。每次迭代中：

1. 臨時保存curr.next避免斷鏈
2. 將當前節點的next指向prev
3. 移動prev和curr指針到下一位置

邊界情況處理

• 空鏈表：直接返回null
• 單節點鏈表：循環一次后返回原頭節點
• 多節點鏈表：完整遍歷直至curr為null

可視化過程

原始鏈表：1 -> 2 -> 3 -> null
反轉過程：

1. prev=null, curr=1, next=2 → 1.next=null
2. prev=1, curr=2, next=3 → 2.next=1
3. prev=2, curr=3, next=null → 3.next=2 最終得到：3 -> 2 -> 1 -> null

using System;public class ListNode {public int Value;public ListNode Next;public ListNode(int value) {Value = value;Next = null;}
}public class LinkedList {private ListNode head;// 添加節點到鏈表尾部public void Append(int value) {//創建list的第一遍才會創建head節點，后續head是有值的。//創建一個Value字段值為value，Next字段為null的head節點，并保存為head（ListNode類）節點if (head == null) {head = new ListNode(value);return;}//head節點賦給current節點，如果當前current.Next字段不為空則往后查找直到為空，目的是為了找到list的末尾；//創建新的末尾節點，并且傳入值賦予該節點ListNode current = head;while (current.Next != null) {current = current.Next;}current.Next = new ListNode(value);//注意：一輪走下來，current的位置應該是倒數第二個節點，head節點始終為第一個節點不移動。}// 反轉鏈表public void Reverse() {ListNode previous = null;ListNode current = head;ListNode nextNode = null;while (current != null) {nextNode = current.Next;  // 暫存下一個節點current.Next = previous;  // 反轉當前節點指針previous = current;       // 將previous移動到當前節點current = nextNode;       // 移動到下一個節點}head = previous;  // 更新頭結點}// 打印鏈表public void PrintList() {ListNode current = head;while (current != null) {Console.Write(current.Value + " ");current = current.Next;}Console.WriteLine();}
}class Program {static void Main(string[] args) {LinkedList list = new LinkedList();list.Append(1);list.Append(2);list.Append(3);list.Append(4);Console.WriteLine("Original List:");list.PrintList();list.Reverse();Console.WriteLine("Reversed List:");list.PrintList();}
}

復雜度對比

方法	時間復雜度	空間復雜度
三指針迭代法	O(n)	O(1)
遞歸法	O(n)	O(n)
棧輔助法	O(n)	O(n)

可視化：https://www.bilibili.com/video/BV1SCtBzyESd/?spm_id_from=333.337.search-card.all.click&vd_source=fc6a649369b5583f6a3050a67ce984cd