鏈表數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方案一、鏈表數(shù)據(jù)結(jié)構(gòu)概述

鏈表是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，通過指針將一組節(jié)點按順序連接起來。每個節(jié)點包含兩部分：存儲數(shù)據(jù)的部分和指向下一個節(jié)點的指針（或前一個節(jié)點的指針，如果是雙向鏈表）。鏈表的主要特點包括：

-動態(tài)內(nèi)存分配：無需預(yù)先分配固定空間，可根據(jù)需要擴(kuò)展或縮減。

-插入和刪除效率高：相比數(shù)組，在頭部或指定位置插入/刪除節(jié)點更高效（O(1)時間復(fù)雜度）。

-隨機(jī)訪問受限：無法像數(shù)組那樣通過索引直接訪問元素（需要從頭遍歷，O(n)時間復(fù)雜度）。

二、鏈表的類型與結(jié)構(gòu)

（一）單鏈表

單鏈表是最基礎(chǔ)的鏈表類型，每個節(jié)點僅包含一個指向下一個節(jié)點的指針。

結(jié)構(gòu)定義（示例代碼）：

classListNode:

def__init__(self,value=0,next_node=None):

self.value=value存儲數(shù)據(jù)

self.next=next_node指向下一個節(jié)點

特點：

1.鏈表頭部為空（None），表示鏈表結(jié)束。

2.刪除最后一個節(jié)點時需遍歷整個鏈表。

（二）雙向鏈表

雙向鏈表每個節(jié)點包含兩個指針：一個指向前一個節(jié)點，一個指向下一個節(jié)點。

結(jié)構(gòu)定義（示例代碼）：

classDoublyListNode:

def__init__(self,value=0,prev_node=None,next_node=None):

self.value=value

self.prev=prev_node指向前一個節(jié)點

self.next=next_node指向下一個節(jié)點

特點：

1.可雙向遍歷，刪除節(jié)點時無需遍歷前驅(qū)節(jié)點。

2.實現(xiàn)復(fù)雜度略高于單鏈表。

（三）循環(huán)鏈表

循環(huán)鏈表是鏈表末尾指向頭部，形成閉環(huán)。分為單循環(huán)鏈表和雙向循環(huán)鏈表。

單循環(huán)鏈表：

-最后一個節(jié)點的`next`指針指向頭部。

-遍歷需檢測是否重復(fù)訪問頭部節(jié)點。

雙向循環(huán)鏈表：

-頭部和尾部互相指向，形成閉環(huán)。

-支持雙向操作，但內(nèi)存消耗更高。

三、鏈表的基本操作

（一）插入操作

1.頭部插入（頭插法）：

-創(chuàng)建新節(jié)點，將其`next`指向原頭部，更新頭部為新節(jié)點。

```python

definsert_at_head(head,value):

new_node=ListNode(value)

new_node.next=head

returnnew_node

```

2.尾部插入（尾插法）：

-遍歷至鏈表末尾，添加新節(jié)點。

```python

definsert_at_tail(head,value):

new_node=ListNode(value)

ifnothead:

returnnew_node

current=head

whilecurrent.next:

current=current.next

current.next=new_node

returnhead

```

3.指定位置插入：

-遍歷至目標(biāo)位置前一個節(jié)點，插入新節(jié)點。

```python

definsert_at_position(head,value,position):

ifposition==0:

returninsert_at_head(head,value)

current=head

for_inrange(position-1):

ifnotcurrent:

raiseValueError("Positionoutofrange")

current=current.next

new_node=ListNode(value)

new_node.next=current.next

current.next=new_node

returnhead

```

（二）刪除操作

1.刪除頭部節(jié)點：

-將頭部指針移動至第二個節(jié)點。

```python

defdelete_at_head(head):

ifnothead:

returnNone

returnhead.next

```

2.刪除尾部節(jié)點：

-遍歷至倒數(shù)第二個節(jié)點，更新其`next`為`None`。

```python

defdelete_at_tail(head):

ifnotheadornothead.next:

returnNone

current=head

whilecurrent.next.next:

current=current.next

current.next=None

returnhead

```

3.刪除指定值節(jié)點：

-遍歷鏈表，找到目標(biāo)節(jié)點并調(diào)整指針。

```python

defdelete_by_value(head,value):

ifnothead:

returnNone

ifhead.value==value:

returnhead.next

current=head

whilecurrent.nextandcurrent.next.value!=value:

current=current.next

ifcurrent.next:

current.next=current.next.next

returnhead

```

（三）遍歷操作

-從頭部開始逐個訪問節(jié)點，直到`next`為`None`。

deftraverse(head):

result=[]

current=head

whilecurrent:

result.append(current.value)

current=current.next

returnresult

四、鏈表應(yīng)用場景

1.棧和隊列的實現(xiàn)：

-棧：利用單鏈表頭部插入和刪除實現(xiàn)LIFO操作。

-隊列：利用單鏈表尾部插入和頭部刪除實現(xiàn)FIFO操作。

2.LRU緩存：

-使用雙向鏈表結(jié)合哈希表實現(xiàn)，快速移動節(jié)點至頭部。

3.數(shù)據(jù)庫索引：

-動態(tài)管理數(shù)據(jù)條目，支持快速插入和刪除。

4.圖數(shù)據(jù)結(jié)構(gòu)：

-使用鄰接表表示圖，節(jié)點通過鏈表連接鄰接點。

五、鏈表優(yōu)缺點總結(jié)

優(yōu)點：

-插入/刪除效率高（O(1)頭部操作）。

-動態(tài)內(nèi)存管理，無需預(yù)分配空間。

缺點：

-隨機(jī)訪問復(fù)雜度高（O(n)）。

-比數(shù)組占用更多內(nèi)存（指針開銷）。

-無法緩存索引位置，只能順序遍歷。

六、代碼示例（完整單鏈表實現(xiàn)）

classListNode:

def__init__(self,value=0,next_node=None):

self.value=value

self.next=next_node

classLinkedList:

def__init__(self):

self.head=None

definsert_at_head(self,value):

new_node=ListNode(value)

new_node.next=self.head

self.head=new_node

definsert_at_tail(self,value):

new_node=ListNode(value)

ifnotself.head:

self.head=new_node

return

current=self.head

whilecurrent.next:

current=current.next

current.next=new_node

defdelete_by_value(self,value):

ifnotself.head:

return

ifself.head.value==value:

self.head=self.head.next

return

current=self.head

whilecurrent.nextandcurrent.next.value!=value:

current=current.next

ifcurrent.next:

current.next=current.next.next

deftraverse(self):

result=[]

current=self.head

whilecurrent:

result.append(current.value)

current=current.next

returnresult

測試用例：

ll=LinkedList()

ll.insert_at_head(3)

ll.insert_at_head(2)

ll.insert_at_tail(4)

print(ll.traverse())[2,3,4]

ll.delete_by_value(3)

print(ll.traverse())[2,4]

三、鏈表的基本操作（續(xù)）

（四）查找操作

查找鏈表中是否存在特定值的節(jié)點，并返回該節(jié)點或其位置信息。

1.查找指定值節(jié)點：

-從頭部開始遍歷，比較每個節(jié)點的值。

-若找到則返回該節(jié)點，否則返回`None`。

```python

deffind_by_value(head,value):

current=head

whilecurrent:

ifcurrent.value==value:

returncurrent

current=current.next

returnNone

```

2.查找指定位置節(jié)點：

-從頭部開始計數(shù)，到達(dá)指定位置返回節(jié)點。

-超出鏈表長度則返回`None`。

```python

deffind_by_position(head,position):

ifposition<0:

raiseValueError("Positionmustbenon-negative")

current=head

index=0

whilecurrentandindex<position:

current=current.next

index+=1

returncurrentifcurrentelseNone

```

（五）反轉(zhuǎn)操作

反轉(zhuǎn)鏈表的節(jié)點順序，適用于單鏈表和雙向鏈表。

1.單鏈表反轉(zhuǎn)（迭代法）：

-使用三個指針：`prev`（前一個節(jié)點）、`current`（當(dāng)前節(jié)點）、`next_temp`（臨時指針）。

-逐個節(jié)點反轉(zhuǎn)指針方向。

```python

defreverse_single_list(head):

prev=None

current=head

whilecurrent:

next_temp=current.next保存下一個節(jié)點

current.next=prev反轉(zhuǎn)指針

prev=current移動prev到當(dāng)前節(jié)點

current=next_temp移動current到下一個節(jié)點

returnprev新頭部

```

2.雙向鏈表反轉(zhuǎn)：

-類似單鏈表，但需同時反轉(zhuǎn)`prev`和`next`指針。

```python

defreverse_doubly_list(head):

prev=None

current=head

whilecurrent:

next_temp=current.next

current.next=prev

current.prev=next_temp

prev=current

current=next_temp

returnprev新頭部

```

（六）合并操作

合并兩個有序鏈表，生成一個新的有序鏈表。

1.合并步驟：

-創(chuàng)建新鏈表頭部`dummy`，使用指針`p1`和`p2`分別指向兩個鏈表頭部。

-比較兩個節(jié)點的值，將較小的節(jié)點添加到新鏈表，并移動對應(yīng)指針。

-處理剩余節(jié)點。

```python

defmerge_two_lists(l1,l2):

dummy=ListNode(0)

current=dummy

p1,p2=l1,l2

whilep1andp2:

ifp1.value<=p2.value:

current.next=p1

p1=p1.next

else:

current.next=p2

p2=p2.next

current=current.next

current.next=p1orp2添加剩余節(jié)點

returndummy.next

```

（七）分割操作

按指定值`x`將鏈表分割為兩個子鏈表：一個包含所有`<=x`的節(jié)點，另一個包含`>x`的節(jié)點。

1.分割步驟：

-創(chuàng)建兩個啞節(jié)點`less_head`和`greater_head`，分別存儲`<=x`和`>x`的節(jié)點。

-遍歷原鏈表，根據(jù)節(jié)點值分配到對應(yīng)子鏈表。

-合并兩個子鏈表，并斷開與原鏈表的連接。

```python

defpartition(head,x):

less_head=ListNode(0)

greater_head=ListNode(0)

less=less_head

greater=greater_head

current=head

whilecurrent:

ifcurrent.value<=x:

less.next=current

less=less.next

else:

greater.next=current

greater=greater.next

current=current.next

greater.next=None斷開連接

less.next=greater_head.next合并鏈表

returnless_head.next

```

四、鏈表應(yīng)用場景（續(xù)）

1.高級數(shù)據(jù)結(jié)構(gòu)構(gòu)建

-多重鏈表：每個節(jié)點包含多個指針（如前驅(qū)、后繼、隨機(jī)指針），用于實現(xiàn)LRU緩存或圖結(jié)構(gòu)。

-哨兵節(jié)點（SentinelNode）：在頭部或尾部添加虛擬節(jié)點，簡化邊界條件處理（如刪除頭部節(jié)點時無需特殊判斷）。

```python

哨兵節(jié)點示例（頭部插入）

definsert_at_head_with_sentinel(head,value):

sentinel=ListNode(0)

sentinel.next=head

insert_at_head(sentinel,value)

returnsentinel.next

```

2.算法問題解決方案

-回文鏈表檢測：

-使用快慢指針找到中點，反轉(zhuǎn)后半鏈表，比較兩半是否相同。

-時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

-環(huán)檢測（Floyd判圈算法）：

-使用兩個指針`slow`（步長1）和`fast`（步長2），若相遇則存在環(huán)。

-可進(jìn)一步找到環(huán)入口（移動慢指針至頭部，同步移動兩指針）。

3.實際系統(tǒng)應(yīng)用

-任務(wù)調(diào)度隊列：

-使用循環(huán)鏈表實現(xiàn)任務(wù)先進(jìn)先出，支持動態(tài)優(yōu)先級調(diào)整（移動節(jié)點位置）。

-內(nèi)存管理：

-操作系統(tǒng)使用鏈表管理空閑內(nèi)存塊，支持快速分配和回收。

五、鏈表優(yōu)化技巧

（一）減少遍歷次數(shù)

-哈希表輔助：對于頻繁查找操作，可使用哈希表記錄節(jié)點值與節(jié)點的映射關(guān)系。

```python

hash_map={}

definsert(head,value):

node=ListNode(value)

hash_map[value]=node

...鏈表插入邏輯

deffind(value):

returnhash_map.get(value)

```

（二）雙向鏈表優(yōu)化

-尾指針緩存：在雙向鏈表中維護(hù)尾指針`tail`，避免遍歷至尾部。

```python

classDoublyLinkedList:

def__init__(self):

self.head=None

self.tail=None

defappend(self,value):

new_node=DoublyListNode(value)

ifnotself.tail:

self.head=self.tail=new_node

else:

self.tail.next=new_node

new_node.prev=self.tail

self.tail=new_node

```

（三）循環(huán)鏈表優(yōu)化

-哨兵節(jié)點應(yīng)用：循環(huán)鏈表也可使用哨兵節(jié)點簡化邊界操作。

```python

單循環(huán)鏈表插入（帶哨兵）

definsert_in_circular_list(head,value):

sentinel=ListNode(0)

sentinel.next=head

current=sentinel

whilecurrent.next!=head:

current=current.next

new_node=ListNode(value)

current.next=new_node

new_node.next=head

returnsentinel.nextifsentinel.next==headelsehead

```

六、代碼示例（完整雙向循環(huán)鏈表實現(xiàn)）

classDoublyListNode:

def__init__(self,value=0,prev_node=None,next_node=None):

self.value=value

self.prev=prev_node

self.next=next_node

classDoublyCircularLinkedList:

def__init__(self):

self.sentinel=DoublyListNode(0)哨兵節(jié)點

self.sentinel.next=self.sentinel初始化為空鏈表

self.sentinel.prev=self.sentinel

defappend(self,value):

new_node=DoublyListNode(value)

tail=self.sentinel.prev

tail.next=new_node

new_node.prev=tail

new_node.next=self.sentinel

self.sentinel.prev=new_node

defprepend(self,value):

new_node=DoublyListNode(value)

first=self.sentinel.next

self.sentinel.next=new_node

new_node.prev=self.sentinel

new_node.next=first

first.prev=new_node

defdelete(self,node):

ifnode==self.sentinel:禁止刪除哨兵

return

prev_node=node.prev

next_node=node.next

prev_node.next=next_node

next_node.prev=prev_node

deffind(self,value):

current=self.sentinel.next

whilecurrent!=self.sentinelandcurrent.value!=value:

current=current.next

returncurrentifcurrent!=self.sentinelelseNone

deftraverse(self):

result=[]

current=self.sentinel.next

whilecurrent!=self.sentinel:

result.append(current.value)

current=current.next

returnresult

測試用例

dll=DoublyCircularLinkedList()

dll.append(1)

dll.append(2)

dll.prepend(0)

print(dll.traverse())[0,1,2]

node=dll.find(1)

dll.delete(node)

print(dll.traverse())[0,2]

七、鏈表與數(shù)組的對比總結(jié)

|特性|鏈表|數(shù)組|

|--------------|-----------------------------|-----------------------------|

|內(nèi)存分配|動態(tài)，按需擴(kuò)展|靜態(tài)或動態(tài)（需連續(xù)內(nèi)存）|

|隨機(jī)訪問|O(n)|O(1)|

|插入/刪除|頭部O(1)，中間O(1)，尾部O(n)|頭部/中間O(n)，尾部O(1)|

|內(nèi)存開銷|每節(jié)點額外指針開銷|無額外開銷|

|緩存友好性|較差（無索引，順序訪問）|較好（連續(xù)內(nèi)存，緩存行優(yōu)化）|

適用場景：

-鏈表：頻繁插入/刪除，內(nèi)存未知或動態(tài)變化（如棧、隊列）。

-數(shù)組：隨機(jī)訪問頻繁，數(shù)據(jù)量固定或變化較?。ㄈ缗判?、查找）。

一、鏈表數(shù)據(jù)結(jié)構(gòu)概述

鏈表是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，通過指針將一組節(jié)點按順序連接起來。每個節(jié)點包含兩部分：存儲數(shù)據(jù)的部分和指向下一個節(jié)點的指針（或前一個節(jié)點的指針，如果是雙向鏈表）。鏈表的主要特點包括：

-動態(tài)內(nèi)存分配：無需預(yù)先分配固定空間，可根據(jù)需要擴(kuò)展或縮減。

-插入和刪除效率高：相比數(shù)組，在頭部或指定位置插入/刪除節(jié)點更高效（O(1)時間復(fù)雜度）。

-隨機(jī)訪問受限：無法像數(shù)組那樣通過索引直接訪問元素（需要從頭遍歷，O(n)時間復(fù)雜度）。

二、鏈表的類型與結(jié)構(gòu)

（一）單鏈表

單鏈表是最基礎(chǔ)的鏈表類型，每個節(jié)點僅包含一個指向下一個節(jié)點的指針。

結(jié)構(gòu)定義（示例代碼）：

classListNode:

def__init__(self,value=0,next_node=None):

self.value=value存儲數(shù)據(jù)

self.next=next_node指向下一個節(jié)點

特點：

1.鏈表頭部為空（None），表示鏈表結(jié)束。

2.刪除最后一個節(jié)點時需遍歷整個鏈表。

（二）雙向鏈表

雙向鏈表每個節(jié)點包含兩個指針：一個指向前一個節(jié)點，一個指向下一個節(jié)點。

結(jié)構(gòu)定義（示例代碼）：

classDoublyListNode:

def__init__(self,value=0,prev_node=None,next_node=None):

self.value=value

self.prev=prev_node指向前一個節(jié)點

self.next=next_node指向下一個節(jié)點

特點：

1.可雙向遍歷，刪除節(jié)點時無需遍歷前驅(qū)節(jié)點。

2.實現(xiàn)復(fù)雜度略高于單鏈表。

（三）循環(huán)鏈表

循環(huán)鏈表是鏈表末尾指向頭部，形成閉環(huán)。分為單循環(huán)鏈表和雙向循環(huán)鏈表。

單循環(huán)鏈表：

-最后一個節(jié)點的`next`指針指向頭部。

-遍歷需檢測是否重復(fù)訪問頭部節(jié)點。

雙向循環(huán)鏈表：

-頭部和尾部互相指向，形成閉環(huán)。

-支持雙向操作，但內(nèi)存消耗更高。

三、鏈表的基本操作

（一）插入操作

1.頭部插入（頭插法）：

-創(chuàng)建新節(jié)點，將其`next`指向原頭部，更新頭部為新節(jié)點。

```python

definsert_at_head(head,value):

new_node=ListNode(value)

new_node.next=head

returnnew_node

```

2.尾部插入（尾插法）：

-遍歷至鏈表末尾，添加新節(jié)點。

```python

definsert_at_tail(head,value):

new_node=ListNode(value)

ifnothead:

returnnew_node

current=head

whilecurrent.next:

current=current.next

current.next=new_node

returnhead

```

3.指定位置插入：

-遍歷至目標(biāo)位置前一個節(jié)點，插入新節(jié)點。

```python

definsert_at_position(head,value,position):

ifposition==0:

returninsert_at_head(head,value)

current=head

for_inrange(position-1):

ifnotcurrent:

raiseValueError("Positionoutofrange")

current=current.next

new_node=ListNode(value)

new_node.next=current.next

current.next=new_node

returnhead

```

（二）刪除操作

1.刪除頭部節(jié)點：

-將頭部指針移動至第二個節(jié)點。

```python

defdelete_at_head(head):

ifnothead:

returnNone

returnhead.next

```

2.刪除尾部節(jié)點：

-遍歷至倒數(shù)第二個節(jié)點，更新其`next`為`None`。

```python

defdelete_at_tail(head):

ifnotheadornothead.next:

returnNone

current=head

whilecurrent.next.next:

current=current.next

current.next=None

returnhead

```

3.刪除指定值節(jié)點：

-遍歷鏈表，找到目標(biāo)節(jié)點并調(diào)整指針。

```python

defdelete_by_value(head,value):

ifnothead:

returnNone

ifhead.value==value:

returnhead.next

current=head

whilecurrent.nextandcurrent.next.value!=value:

current=current.next

ifcurrent.next:

current.next=current.next.next

returnhead

```

（三）遍歷操作

-從頭部開始逐個訪問節(jié)點，直到`next`為`None`。

deftraverse(head):

result=[]

current=head

whilecurrent:

result.append(current.value)

current=current.next

returnresult

四、鏈表應(yīng)用場景

1.棧和隊列的實現(xiàn)：

-棧：利用單鏈表頭部插入和刪除實現(xiàn)LIFO操作。

-隊列：利用單鏈表尾部插入和頭部刪除實現(xiàn)FIFO操作。

2.LRU緩存：

-使用雙向鏈表結(jié)合哈希表實現(xiàn)，快速移動節(jié)點至頭部。

3.數(shù)據(jù)庫索引：

-動態(tài)管理數(shù)據(jù)條目，支持快速插入和刪除。

4.圖數(shù)據(jù)結(jié)構(gòu)：

-使用鄰接表表示圖，節(jié)點通過鏈表連接鄰接點。

五、鏈表優(yōu)缺點總結(jié)

優(yōu)點：

-插入/刪除效率高（O(1)頭部操作）。

-動態(tài)內(nèi)存管理，無需預(yù)分配空間。

缺點：

-隨機(jī)訪問復(fù)雜度高（O(n)）。

-比數(shù)組占用更多內(nèi)存（指針開銷）。

-無法緩存索引位置，只能順序遍歷。

六、代碼示例（完整單鏈表實現(xiàn)）

classListNode:

def__init__(self,value=0,next_node=None):

self.value=value

self.next=next_node

classLinkedList:

def__init__(self):

self.head=None

definsert_at_head(self,value):

new_node=ListNode(value)

new_node.next=self.head

self.head=new_node

definsert_at_tail(self,value):

new_node=ListNode(value)

ifnotself.head:

self.head=new_node

return

current=self.head

whilecurrent.next:

current=current.next

current.next=new_node

defdelete_by_value(self,value):

ifnotself.head:

return

ifself.head.value==value:

self.head=self.head.next

return

current=self.head

whilecurrent.nextandcurrent.next.value!=value:

current=current.next

ifcurrent.next:

current.next=current.next.next

deftraverse(self):

result=[]

current=self.head

whilecurrent:

result.append(current.value)

current=current.next

returnresult

測試用例：

ll=LinkedList()

ll.insert_at_head(3)

ll.insert_at_head(2)

ll.insert_at_tail(4)

print(ll.traverse())[2,3,4]

ll.delete_by_value(3)

print(ll.traverse())[2,4]

三、鏈表的基本操作（續(xù)）

（四）查找操作

查找鏈表中是否存在特定值的節(jié)點，并返回該節(jié)點或其位置信息。

1.查找指定值節(jié)點：

-從頭部開始遍歷，比較每個節(jié)點的值。

-若找到則返回該節(jié)點，否則返回`None`。

```python

deffind_by_value(head,value):

current=head

whilecurrent:

ifcurrent.value==value:

returncurrent

current=current.next

returnNone

```

2.查找指定位置節(jié)點：

-從頭部開始計數(shù)，到達(dá)指定位置返回節(jié)點。

-超出鏈表長度則返回`None`。

```python

deffind_by_position(head,position):

ifposition<0:

raiseValueError("Positionmustbenon-negative")

current=head

index=0

whilecurrentandindex<position:

current=current.next

index+=1

returncurrentifcurrentelseNone

```

（五）反轉(zhuǎn)操作

反轉(zhuǎn)鏈表的節(jié)點順序，適用于單鏈表和雙向鏈表。

1.單鏈表反轉(zhuǎn)（迭代法）：

-使用三個指針：`prev`（前一個節(jié)點）、`current`（當(dāng)前節(jié)點）、`next_temp`（臨時指針）。

-逐個節(jié)點反轉(zhuǎn)指針方向。

```python

defreverse_single_list(head):

prev=None

current=head

whilecurrent:

next_temp=current.next保存下一個節(jié)點

current.next=prev反轉(zhuǎn)指針

prev=current移動prev到當(dāng)前節(jié)點

current=next_temp移動current到下一個節(jié)點

returnprev新頭部

```

2.雙向鏈表反轉(zhuǎn)：

-類似單鏈表，但需同時反轉(zhuǎn)`prev`和`next`指針。

```python

defreverse_doubly_list(head):

prev=None

current=head

whilecurrent:

next_temp=current.next

current.next=prev

current.prev=next_temp

prev=current

current=next_temp

returnprev新頭部

```

（六）合并操作

合并兩個有序鏈表，生成一個新的有序鏈表。

1.合并步驟：

-創(chuàng)建新鏈表頭部`dummy`，使用指針`p1`和`p2`分別指向兩個鏈表頭部。

-比較兩個節(jié)點的值，將較小的節(jié)點添加到新鏈表，并移動對應(yīng)指針。

-處理剩余節(jié)點。

```python

defmerge_two_lists(l1,l2):

dummy=ListNode(0)

current=dummy

p1,p2=l1,l2

whilep1andp2:

ifp1.value<=p2.value:

current.next=p1

p1=p1.next

else:

current.next=p2

p2=p2.next

current=current.next

current.next=p1orp2添加剩余節(jié)點

returndummy.next

```

（七）分割操作

按指定值`x`將鏈表分割為兩個子鏈表：一個包含所有`<=x`的節(jié)點，另一個包含`>x`的節(jié)點。

1.分割步驟：

-創(chuàng)建兩個啞節(jié)點`less_head`和`greater_head`，分別存儲`<=x`和`>x`的節(jié)點。

-遍歷原鏈表，根據(jù)節(jié)點值分配到對應(yīng)子鏈表。

-合并兩個子鏈表，并斷開與原鏈表的連接。

```python

defpartition(head,x):

less_head=ListNode(0)

greater_head=ListNode(0)

less=less_head

greater=greater_head

current=head

whilecurrent:

ifcurrent.value<=x:

less.next=current

less=less.next

else:

greater.next=current

greater=greater.next

current=current.next

greater.next=None斷開連接

less.next=greater_head.next合并鏈表

returnless_head.next

```

四、鏈表應(yīng)用場景（續(xù)）

1.高級數(shù)據(jù)結(jié)構(gòu)構(gòu)建

-多重鏈表：每個節(jié)點包含多個指針（如前驅(qū)、后繼、隨機(jī)指針），用于實現(xiàn)LRU緩存或圖結(jié)構(gòu)。

-哨兵節(jié)點（SentinelNode）：在頭部或尾部添加虛擬節(jié)點，簡化邊界條件處理（如刪除頭部節(jié)點時無需特殊判斷）。

```python

哨兵節(jié)點示例（頭部插入）

definsert_at_head_with_sentinel(head,value):

sentinel=ListNode(0)

sentinel.next=head

insert_at_head(sentinel,value)

returnsentinel.next

```

2.算法問題解決方案

-回文鏈表檢測：

-使用快慢指針找到中點，反轉(zhuǎn)后半鏈表，比較兩半是否相同。

-時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

-環(huán)檢測（Floyd判圈算法）：

-使用兩個指針`slow`（步長1）和`fast`（步長2），若相遇則存在環(huán)。

-可進(jìn)一步找到環(huán)入口（移動慢指針至頭部，同步移動兩指針）。

3.實際系統(tǒng)應(yīng)用

-任務(wù)調(diào)度隊列：

-使用循環(huán)鏈表實現(xiàn)任務(wù)先進(jìn)先出，支持動態(tài)優(yōu)先級調(diào)整（移動節(jié)點位置）。

-內(nèi)存管理：

-操作系統(tǒng)使用鏈表管理空閑內(nèi)存塊，支持快速分配和回收。

五、鏈表優(yōu)化技巧

（一）減少遍歷次數(shù)

-哈希表輔助：對于頻繁查找操作，可使用哈希表記錄節(jié)點值與節(jié)點的映射關(guān)系。

```python

hash_map={}

definsert(head,value):

node=ListNode(value)

hash_map[value]=node

...鏈表插入邏輯

deffind(value):

returnhash_map.get(value)

```

（二）雙向鏈表優(yōu)化

-尾指針緩存：在雙向鏈表中維護(hù)尾指針`tail`，避免遍歷至尾部。

```python

classDoublyLinkedList:

def__init__(self):

self.head=None

self.tail=None

defappend(self,value):

new_node=DoublyListNode(value)

ifnotself.tail:

self.head=self.tail=new_node

else:

self.tail.next=new_node

new_node.prev=self.tail

self.tail=new_node

```

（三）循環(huán)鏈表優(yōu)化

-哨兵節(jié)點應(yīng)用：循環(huán)鏈表也可使用哨兵節(jié)點簡化邊界操作。

```python

單循環(huán)鏈表插入（帶哨兵）

definsert_in_circular_list(head,value):

sentinel=ListNode(0)

sentinel.next=head

current=sentinel

whilecurrent.next!=head:

current=current.next

new_node=ListNode(value)

current.next=new_node

new_node.next=head

returnsentinel.nextifsentinel.next==headelsehead

```

六、代碼示例（完整雙向循環(huán)鏈表實現(xiàn)）

classDoublyListNode: