這是一道鏈結串列問題,要求將鏈結串列中每兩個相鄰的節點進行交換,並返回新的串列頭。重要的是,不能改變節點內的值(val),只能透過改變節點的指標(next)來完成交換操作。
這題的核心是指標操作(Pointer Manipulation)。這需要一組指標來幫助完成兩個相鄰節點(例如:A和B)之間的交換,同時還需要確保交換後的B能夠正確地連接到下一個未處理的節點組(例如:C和D)之前。
為了處理串列頭節點可能參與交換(即新的串列頭會改變)的情況,通常會建立一個虛擬頭節點(或稱哨兵節點,dummy),並讓它指向原始串列的頭節點。這樣一來,,無論原來的頭節點是否被交換,新的串列頭永遠是dummy.next。
接著,需要一個指標,例如prev,來追蹤前一個已交換組的末尾節點(或虛擬頭節點),這樣它才能連接到當前交換組的新頭節點。
假設當前要交換的兩個節點是A和B,A的前一個節點是prev。A指向B,而B指向C(下一個未處理的節點)。這題的目標是:prev -> B -> A -> C。
這題我使用prev、node1(即A)和node2(即B)三個指標
1.node1(A)<- prev.next
2.node2(B)<- node1.next
3.步驟1:prev -> B:將已交換組的尾部(prev)指向新組的頭(node2)。
prev.next = node2;
4.步驟2:A -> C:將A指向B的下一個節點C,也就是下一個未處理的組的頭。
node1.next = node2.next;
5.步驟3:B -> A:將B指向A,完成交換。
node2.next = node1;
6.更新prev:將prev移到當前交換組的末尾(現在是A),為下一次迭代做準備。
prev = node1;
當prev.next或prev.next.next變成null時,表示沒有足夠的節點進行下一組交換,迭代結束。