leetcode-explore-learn-數(shù)據(jù)結(jié)構(gòu)-鏈表3

• 1.反轉(zhuǎn)一個鏈表
• 2.移除鏈表元素
• 3.奇偶鏈表
• 4.回文鏈表
• 5.小結(jié)

本系列博文為leetcode-explore-learn子欄目學(xué)習(xí)筆記，如有不詳之處，請參考leetcode官網(wǎng)：https://leetcode-cn.com/explore/learn/card/linked-list/

所有例題的編程語言為python

1.反轉(zhuǎn)一個鏈表

leetcode 206
思路1： 迭代求解，將當(dāng)前結(jié)點(diǎn)next信息保存下來，然后將前一個節(jié)點(diǎn)的信息存入當(dāng)前結(jié)點(diǎn)的next中。更新當(dāng)前結(jié)點(diǎn)。

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None:return headpre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_nodereturn pre_node

思路2：
遞歸：假設(shè)鏈表的其余部分都已經(jīng)被翻轉(zhuǎn)，現(xiàn)在該如何翻轉(zhuǎn)它前面的部分。由最后一個開始往前不斷翻轉(zhuǎn)

class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None or head.next==None:return headp=self.reverseList(head.next) # 記錄最后一個結(jié)點(diǎn)作為頭指針用的。head.next.next=headhead.next=Nonereturn p

2.移除鏈表元素

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。
思路：遍歷鏈表的每一結(jié)點(diǎn)，如果值等于給定值將其刪除即可。
注意點(diǎn)：要刪除鏈表節(jié)點(diǎn)時，可以使用啞結(jié)點(diǎn)技巧，防止刪原鏈表的頭結(jié)點(diǎn)。最后返回時，返回dummy.next即可。

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""dummy=ListNode(0)dummy.next=headpre_node=dummycur_node=dummy.nextwhile(cur_node):next_node=cur_node.nextif cur_node.val==val:pre_node.next=next_node # 刪除結(jié)點(diǎn)else:pre_node=cur_nodecur_node=next_nodereturn dummy.next

3.奇偶鏈表

給定一個單鏈表，把所有奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)（節(jié)點(diǎn) 編號的奇偶性）分別排在一起。
思路1：原來的鏈表分成奇偶兩個子鏈表，然后將偶鏈表鏈接到奇鏈表后面。
沒有使用額外的空間，直接從原來的鏈表中截取。

# Definition for singly-linked list. class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def oddEvenList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None:return headeven_h=ListNode(0)even_node=even_hcur_node=headi=1while(cur_node):next_node=cur_node.nextif i %2==0:cur_node.next=None # 將node.next的值給設(shè)置為零，能防止成環(huán)even_node.next=cur_nodeeven_node=even_node.nextpre_node.next=next_nodeelse:pre_node=cur_nodecur_node=next_nodei+=1cur_node=head.nextpre_node=headwhile(cur_node):print(pre_node.val)pre_node=cur_nodecur_node=cur_node.nextpre_node.next=even_h.nextreturn head

4.回文鏈表

判斷一個鏈表是否為回文鏈表。
o(n)時間復(fù)雜度，o(1)空間復(fù)雜度

思路1：可以先把鏈表裝進(jìn)數(shù)組中，判斷數(shù)組中元素是否構(gòu)成回文。數(shù)組的前后遍歷比單鏈表方便。時間復(fù)雜度o(n)，空間復(fù)雜度o(n)

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return Truelst=[]p=headwhile(p):lst.append(p.val)p=p.nextreturn lst==lst[::-1]

思路2：翻轉(zhuǎn)原鏈表，對照兩個鏈表是否一致，如果回文鏈表應(yīng)該是一致的，反之原鏈表不為回文鏈表。時間復(fù)雜度o(n),空間復(fù)雜度o(n)

# Definition for singly-linked list. class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if head==None or head.next==None:return True# 備份原鏈表head_be=ListNode(0)node=headnode_be=head_be while(node):node_be.next=ListNode(node.val)node_be=node_be.nextnode=node.next# 轉(zhuǎn)置原鏈表pre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_node# 比較兩個鏈表node_be=head_be.nextnode_af=pre_nodewhile(node_be and node_af):if node_be.val!=node_af.val:return Falsenode_be=node_be.nextnode_af=node_af.nextreturn True

思路三：避免使用 O(n)O(n) 額外空間的方法就是改變輸入。

我們可以將鏈表的后半部分反轉(zhuǎn)（修改鏈表結(jié)構(gòu)），然后將前半部分和后半部分進(jìn)行比較。比較完成后我們應(yīng)該將鏈表恢復(fù)原樣。雖然不需要恢復(fù)也能通過測試用例，因?yàn)槭褂迷摵瘮?shù)的人不希望鏈表結(jié)構(gòu)被更改。

class Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return True# 計算鏈表長度p1=headn=1while(p1.next):p1=p1.nextn+=1p1=headp2=headif n==2:if head.val==head.next.val:return Trueelse:return False# 找鏈表中點(diǎn)for i in range(int(round(n/2.0))-1): # 0p1=p1.nexthalf_end=p1 # 前一半鏈表的最后一個節(jié)點(diǎn)# 翻轉(zhuǎn)后一半鏈表p1=p1.nextpre_node=Nonefor i in range(int(n/2.0)): # 0,1next_node=p1.nextp1.next=pre_nodepre_node=p1p1=next_nodehalf_end.next=pre_nodep1=head# 比較前一半和翻轉(zhuǎn)后的后一半。for i in range(int(round(n/2.0))): # 0,1p1=p1.nextfor i in range(int(n/2)):# 0,1if p1.val!=p2.val:return Falsep1=p1.nextp2=p2.nextreturn True

5.小結(jié)

1.使用鏈表時不易調(diào)試，自己多嘗試幾個測試用例總是很有用的，通過輸出鏈表節(jié)點(diǎn)的值來觀測代碼運(yùn)行情況。

2.多指針時，為指針設(shè)定合適的名稱，防止自己被搞混

3.單鏈表操作時，儲存前一個節(jié)點(diǎn)的信息往往是有效的。

總結(jié)

以上是生活随笔為你收集整理的算法(11)-leetcode-explore-learn-数据结构-链表的经典问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。