劍值offer學習

單連結串列的快速排序

單連結串列的特點是:單向。設頭結點位head,則最後一個節點的next指向NULL。如果只知道頭結點head,請問怎麼將該連結串列排序? 設結點結構為: struct Node{ int key; Node* next; }; 那麼一般人見到這種題目,立馬就會想到指標交換。是的,大家被指標交換的題目 […]

連結串列反轉

如何把一個單連結串列進行反轉? 方法1:將單連結串列儲存為陣列,然後按照陣列的索引逆序進行反轉。 方法2:使用3個指標遍歷單連結串列,逐個連結點進行反轉。 方法3:從第2個節點到第N個節點,依次逐節點插入到第1個節點(head節點)之後,最後將第一個節點挪到新表的表尾。 方法4:   遞迴 […]

二叉搜尋樹轉換成雙向連結串列

題目 輸入一棵二叉搜尋樹,將該二叉搜尋樹轉換成一個排序的雙向連結串列。 要求不能建立任何新的結點,只能調整樹中結點指標的指向。 思路 中序遍歷:把一棵二叉排序樹看成三個部分,根節點,右子樹,左子樹, 根節點的左指標指向左子樹的形成連結串列的最後一個節點, 根節點的右孩子指向右子樹形成連結串列的第一個 […]