在PHP中,經常會涉及到鏈表的操作,其中交換鏈表的兩個節點是一個常見的問題。假設有一個鏈表1->2->3->4->5,現在我們需要交換第二個節點2和第四個節點4,那么該如何實現呢?
我們可以通過三個指針來完成該操作,具體實現如下:
這段代碼的核心就是while循環中的內容:先記錄當前節點和下一個節點,然后交換這兩個節點,最后向前移動三個指針。鏈表交換完成后,我們可以打印出交換后的結果:1 4 3 2 5。
除了上面的方法外,還有一種更簡單的方式可以實現交換鏈表節點的功能,如下所示:
這種方法利用遞歸的思想來實現,其核心也是交換相鄰的兩個節點,并依次向前移動鏈表的指針。
總體來說,以上兩種方法都是較為常見的實現鏈表節點交換的方法。在使用中,我們可以根據實際需求來選擇合適的方法。
我們可以通過三個指針來完成該操作,具體實現如下:
class ListNode{
public $val;
public $next;
function __construct($val){
$this->val=$val;
$this->next=null;
}
}
function swapPairs($head){
$dummy = new ListNode(0);
$dummy->next = $head;
$prev = $dummy;
while($head && $head->next){
$first = $head;
$second = $head->next;
$prev->next = $second;
$first->next = $second->next;
$second->next = $first;
$prev = $first;
$head = $first->next;
}
return $dummy->next;
}
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);
$result = swapPairs($head);
while($result !==null){
echo $result->val." ";
$result = $result->next;
}
這段代碼的核心就是while循環中的內容:先記錄當前節點和下一個節點,然后交換這兩個節點,最后向前移動三個指針。鏈表交換完成后,我們可以打印出交換后的結果:1 4 3 2 5。
除了上面的方法外,還有一種更簡單的方式可以實現交換鏈表節點的功能,如下所示:
function swapPairs($head){
if($head == null || $head->next == null) return $head;
$cur = $head->next;
$head->next = swapPairs($cur->next);
$cur->next = $head;
return $cur;
}
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);
$result = swapPairs($head);
while($result !==null){
echo $result->val." ";
$result = $result->next;
}
這種方法利用遞歸的思想來實現,其核心也是交換相鄰的兩個節點,并依次向前移動鏈表的指針。
總體來說,以上兩種方法都是較為常見的實現鏈表節點交換的方法。在使用中,我們可以根據實際需求來選擇合適的方法。
上一篇php 從a循環到z
下一篇php 交互模式