鏈表理論基礎(chǔ)?

Q：什么是鏈表？

A：鏈表是由一系列結(jié)點(diǎn)組成的。每一個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)和指針。

203.移除鏈表元素?

題目：

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val ，請(qǐng)你刪除鏈表中所有滿(mǎn)足 Node.val == val 的節(jié)點(diǎn)，并返回 新的頭節(jié)點(diǎn) 。

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6

輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1

輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7

輸出：[]

思路：

????????需要遍歷，當(dāng)元素等于val，指針指向下下個(gè)元素的。第一次學(xué)習(xí)并使用鏈表，需要熟悉如何建立鏈表，如何遍歷元素。所以一刷基本屬于照貓畫(huà)虎，但是重要的掌握思路，我也不求一遍就通透。

代碼：

# Definition for singly-linked list.  定義單鏈表
# class ListNode:   定義鏈表的類(lèi)
#     def __init__(self, val=0, next=None):  
#     鏈表中的數(shù)據(jù)和指針，next=None是最后一個(gè)結(jié)點(diǎn)的屬性，即指針指向空\(chéng)
#     但是在此處，有2種指向：如果有下一個(gè)結(jié)點(diǎn)，可以再給next賦值，沒(méi)有就讓它默認(rèn)指向空
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 創(chuàng)建虛擬頭部節(jié)點(diǎn)，簡(jiǎn)化刪除過(guò)程，因?yàn)橛锌赡艿谝粋€(gè)結(jié)點(diǎn)就需要?jiǎng)h除dummy_head = ListNode(next=head)# 遍歷鏈表，刪除val的值cur = dummy_headwhile cur.next:  # 只要當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)不為空，就循環(huán)if cur.next.val == val:cur.next = cur.next.next  # 跳過(guò)val值，也就是刪除該值的動(dòng)作else:cur = cur.next  # 如果不等與val,繼續(xù)遍歷return dummy_head.next  # 返回虛擬頭節(jié)點(diǎn)的指針，也就是去除了val值的新鏈表

?707.設(shè)計(jì)鏈表?

題目：

你可以選擇使用單鏈表或者雙鏈表，設(shè)計(jì)并實(shí)現(xiàn)自己的鏈表。

單鏈表中的節(jié)點(diǎn)應(yīng)該具備兩個(gè)屬性：val 和 next 。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。

如果是雙向鏈表，則還需要屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)下標(biāo)從 0 開(kāi)始。

實(shí)現(xiàn) MyLinkedList 類(lèi)：

MyLinkedList() 初始化 MyLinkedList 對(duì)象。

int get(int index) 獲取鏈表中下標(biāo)為 index 的節(jié)點(diǎn)的值。如果下標(biāo)無(wú)效，則返回 -1 。

void addAtHead(int val) 將一個(gè)值為 val 的節(jié)點(diǎn)插入到鏈表中第一個(gè)元素之前。在插入完成后，新節(jié)點(diǎn)會(huì)成為鏈表的第一個(gè)節(jié)點(diǎn)。

void addAtTail(int val) 將一個(gè)值為 val 的節(jié)點(diǎn)追加到鏈表中作為鏈表的最后一個(gè)元素。

void addAtIndex(int index, int val) 將一個(gè)值為 val 的節(jié)點(diǎn)插入到鏈表中下標(biāo)為 index 的節(jié)點(diǎn)之前。如果 index 等于鏈表的長(zhǎng)度，那么該節(jié)點(diǎn)會(huì)被追加到鏈表的末尾。如果 index 比長(zhǎng)度更大，該節(jié)點(diǎn)將 不會(huì)插入 到鏈表中。

void deleteAtIndex(int index) 如果下標(biāo)有效，則刪除鏈表中下標(biāo)為 index 的節(jié)點(diǎn)。

示例：

輸入

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]

[[], [1], [3], [1, 2], [1], [1], [1]]

輸出

[null, null, null, null, 2, null, 3]

解釋

MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addAtHead(1);

myLinkedList.addAtTail(3);

myLinkedList.addAtIndex(1, 2);??? // 鏈表變?yōu)?1->2->3

myLinkedList.get(1);????????????? // 返回 2

myLinkedList.deleteAtIndex(1);??? // 現(xiàn)在，鏈表變?yōu)?1->3

myLinkedList.get(1);????????????? // 返回 3

思路：

這道題目非常經(jīng)典，涵蓋了鏈表基本的操作。題目看起來(lái)復(fù)雜，基本是如下幾個(gè)問(wèn)題：

1. 在頭部插入新節(jié)點(diǎn)
2. 在尾部插入新節(jié)點(diǎn)
3. 在中間插入新節(jié)點(diǎn)
4. 刪除指定的結(jié)點(diǎn)

卡哥強(qiáng)調(diào)：需要注意的是新增結(jié)點(diǎn)的時(shí)候，要讓新結(jié)點(diǎn)先指向下一個(gè)結(jié)點(diǎn)，再讓上一個(gè)結(jié)點(diǎn)指向新節(jié)點(diǎn)，順序很重要。

代碼：

1、單鏈表

# 定義一個(gè)鏈表:
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:  # 單鏈表# 初始化鏈表def __init__(self):self.dummy_head = ListNode()  # 建立虛擬節(jié)點(diǎn)self.size = 0  # 初始化結(jié)點(diǎn)的長(zhǎng)度為0，也就是剛開(kāi)始鏈表沒(méi)有任何數(shù)字# 獲取下標(biāo)的值def get(self, index: int) -> int:if index < 0 or index >= self.size:  # 在鏈表之外的范圍，不符合return -1cur = self.dummy_head.next  # 必須要用self,for i in range(index):cur = cur.next  # 表示將指針移動(dòng)到下一個(gè)結(jié)點(diǎn)return cur.val# 在頭部新增一個(gè)結(jié)點(diǎn)def addAtHead(self, val: int) -> None:self.dummy_head.next =ListNode(val,self.dummy_head.next)  # 虛擬結(jié)點(diǎn)指向新節(jié)點(diǎn)self.size += 1## 在頭部新增一個(gè)結(jié)點(diǎn)#  加入自己理解寫(xiě)的，看下來(lái)和雙鏈表比較接近# def addAtHead(self, val: int) -> None:#     new_node = ListNode(val)  # 創(chuàng)建新節(jié)點(diǎn)#     new_node.next = self.dummy_head.next  # 新節(jié)點(diǎn)指向頭節(jié)點(diǎn)#     self.dummy_head.next = new_node  # 虛擬結(jié)點(diǎn)指向新節(jié)點(diǎn)#     self.size += 1# 在尾部添加一個(gè)結(jié)點(diǎn)def addAtTail(self, val: int) -> None:# new_node_tail = ListNode(val)cur = self.dummy_head  # 指針當(dāng)前指向虛擬節(jié)點(diǎn)while cur.next:  # 當(dāng)當(dāng)前指針沒(méi)有指向空，則一直循環(huán)cur = cur.nextcur.next = ListNode(val)self.size += 1# 在指定下標(biāo)添加一個(gè)結(jié)點(diǎn)def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncur = self.dummy_head# new_node3 = ListNode(val)for i in range(index):cur = cur.nextcur.next = ListNode(val,cur.next)self.size += 1# 刪除指定下標(biāo)的結(jié)點(diǎn)def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:    # 這里的'='非常重要！debug了很久很久……returncur = self.dummy_headfor i in range(index):cur = cur.next   # 在鏈表中遍歷至索引位置的前一個(gè)結(jié)點(diǎn)cur.next = cur.next.next  # index這個(gè)位置的數(shù)就等于它的下一個(gè)數(shù)，就實(shí)現(xiàn)了刪除index指向的數(shù)self.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)class MyLinkedList:

? 2、雙鏈表

……暫時(shí)還不能完全理解雙鏈表，先把單鏈表學(xué)會(huì)了再來(lái)……

【總結(jié)】

????????鏈表的基本操作和思路已經(jīng)理解，但是一些臨界的條件考慮的還不夠周全，甚至寫(xiě)起代碼相當(dāng)生澀。繼續(xù)加油吧！

?206.反轉(zhuǎn)鏈表?

題目：

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]

輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]

輸出：[2,1]

示例 3：

輸入：head = []

輸出：[]

思路：

讓每一個(gè)結(jié)點(diǎn)的指針指向前一個(gè)結(jié)點(diǎn)。

代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:prev=None  # 前一個(gè)結(jié)點(diǎn)cur=head  # 當(dāng)前結(jié)點(diǎn)next=None  # 下一個(gè)結(jié)點(diǎn)while cur:next=cur.nextcur.next=prev  # 實(shí)現(xiàn)反轉(zhuǎn)prev=curcur=nextreturn prev

今日總結(jié)：

????????學(xué)到新知識(shí)的感覺(jué)很踏實(shí)，但是一次也沒(méi)有辦法消化三道題，對(duì)我來(lái)說(shuō)，在學(xué)習(xí)的過(guò)程中手寫(xiě)是很有用的，學(xué)習(xí)到鏈表的基礎(chǔ)知識(shí)并在做題中了解邏輯，明日繼續(xù)加油！