LeetCode：鏈表（2）
文章目錄
- LeetCode：鏈表（2）
- 237.洗掉鏈表中的節點
- 203.移除鏈表元素
- 160. 相交鏈表
- 234. 回文鏈表
237.洗掉鏈表中的節點
剛開始看沒搞懂啥意思，，，，，，要洗掉的節點已經給你找出來了，只需要將其覆寫就可以
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
206.反轉鏈表
思路1：三個指標
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre,cur = None,head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
203.移除鏈表元素
思路：前后指標
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
while head and head.val==val:
head = head.next
if not head: return head
pre,cur = head,head.next
while cur:
if cur.val == val:
pre.next=cur.next
else:
pre = cur
cur = cur.next
return head
160. 相交鏈表
思路1：方法可行，但是超出時間限制，，，
#第一思路暴力法
cur1,cur2 = headA,headB
while cur1:
while cur2:
if cur2 is cur1:
return cur2
cur2 = cur2.next
cur2 = headB
cur1 = cur1.next
return cur1
思考：如果出現兩者永不相交的情況的話，就會出現死回圈，
改進：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
#第一思路暴力法
cur1,cur2 = headA,headB
while cur1 is not cur2:
cur1 = cur1.next if cur1 else headB
cur2 = cur2.next if cur2 else headA
return cur1
思路解讀：為什么會出現相互賦值初始頭結點的情況？
短鏈表走到盡頭后繼續走長鏈表，就相當于短鏈表+長鏈表，長鏈表走到盡頭后又走短鏈表，相當于長鏈表+短鏈表，所以重新走兩次其實本質上還是相當于走兩次新的拼接的互補鏈表，一定會找到交點，
如果出現不相交的情況：
因為headA+headB和headB+ headA長度一定是相等的，所以最后一定會出現同時為None的情況來確保不會出現死回圈，
方法2：字典模擬哈希表
將其中一個鏈表存盤到字典中，另一個遍歷，看是否存在于字典，若存在，則說明有共同節點；若不存在，則說明沒有共同節點，
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
#字典模擬哈希表
dic = {}
cur1,cur2 = headA,headB
while cur1:
dic[cur1] = 1
cur1 = cur1.next
while cur2:
if cur2 in dic:
return cur2
cur2 = cur2.next
return cur2
234. 回文鏈表
方法1：將值讀出存盤為字串
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
str1 = ''
cur = head
while cur:
str1 += (str(cur.val))
cur = cur.next
num = len(str1)
return str1 == str1[::-1]
劍指offer22.鏈表中倒數第k個節點
方法1：
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
count = 1-k
cur = head
while cur:
cur = cur.next
count +=1
cur = head
while count:
if count == 1: return cur
count -= 1
cur = cur.next
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/279808.html
標籤：python
上一篇：2017年NBA球員資料分析