多種解法破解鏈表
- 2019 年 10 月 5 日
- 筆記
多種解法破解鏈表
0.說在前面1.旋轉鏈表2.相交鏈表3.作者的話
0.說在前面
我們算法已經到了leetcode攀登之旅(21)!本周還差一次刷題推送,這篇就是,沒錯,讓各位久等了,這次放的可是多種解法乾貨!!!
這次刷的題為旋轉鏈表與相交鏈表!!! 說明一下,下面有個圖文是我跟范大大組織的一次算法訓練周計劃!有想法的可以留言哈!
1.旋轉鏈表
題目
給定一個鏈表,旋轉鏈表,將鏈表每個節點向右移動 k 個位置,其中 k 是非負數。
示例 1:
輸入: 1->2->3->4->5->NULL, k = 2 輸出: 4->5->1->2->3->NULL 解釋: 向右旋轉 1 步: 5->1->2->3->4->NULL 向右旋轉 2 步: 4->5->1->2->3->NULL
示例 2:
輸入: 0->1->2->NULL, k = 4 輸出: 2->0->1->NULL 解釋: 向右旋轉 1 步: 2->0->1->NULL 向右旋轉 2 步: 1->2->0->NULL 向右旋轉 3 步: 0->1->2->NULL 向右旋轉 4 步: 2->0->1->NULL
思路
對於這個題目我想出了兩種解法,現在分享一下。
解法一,讓我想起了遞歸,然後未提交之前分析了一下複雜度,自己都覺得通過不了,你們懂的,遞歸效率不高!但是思路需要學會!
解法二,於是我開始想解法二,便發現了這道題的貓膩,那就是右移旋轉k位置,如果是鏈表整數倍,那麼旋轉後鏈表不變,而如果不是鏈表整數倍,那麼我們算出他的餘數(k除以鏈表長度),真正移動的就是這個餘數!
那麼下面一起來實戰吧!
實現
【遞歸實現】
這個算法,僅供研讀學習思路,通不過的哈,超時。。。遞歸算法效率本身就不高!
class Solution(object): def rotateRight(self, head, k): if k == 0 or head is None or head.next is None: return head for i in range(k): head = self.rightShift(head) return head def rightShift(self, head): pre = head curr = head.next while curr: if curr.next is None: curr.next = head pre.next = None return curr pre = pre.next curr = curr.next return curr
【獲取真正k實現】
這個算法的關鍵在於,獲取真正的右移次數,可以有效的解決時間複雜度問題!所以這裡我將我的這個算法命名為獲取真正k實現!
算法思路實現步驟:
- 特殊情況處理
k為0,鏈表為空或者只有一個結點旋轉後,還是本身,所以直接返回!
- 非特殊情況處理
(1)循環鏈表一次,獲取鏈表長度!
pre代表右旋轉後的鏈表的最後一個結點,curr代表右旋轉的後面鏈表前置的頭結點!
這裡舉個實際例子,如圖所示:
class Solution(object): def rotateRight(self, head, k): if k==0 or head is None or head.next is None: return head p=head size=0 while p: size+=1 p=p.next # 所循環的真實k # 真實k為原始k除以鏈表長度取模 k=k%size p=head pre=head curr=head.next ''' (1)真實k如果不為0,參照算法圖 (2)真實k如果為0,也就是原始k能夠整除鏈表長度, 那麼此時的節點旋轉後還是原鏈表,直接返回原鏈表 ''' if k: for i in range(size-k): pre=p curr=p.next p=p.next # 右旋轉後的鏈表的最後一個結點next指向空 pre.next=None # 保存最終鏈表的頭節點 newhead=curr # 循環後面移動到前面鏈表的所有結點,直到最後 while curr.next: curr=curr.next # 讓上述尾部結點連接原先的頭節點,構成一個完整鏈表 curr.next=head return newhead return head
算法分析
遞歸實現的時間複雜度為O(k*n),空間複雜度為O(n)
獲取真實k實現的時間複雜度為O(n),空間複雜度為O(n)
2.相交鏈表
題目
編寫一個程序,找到兩個單鏈表相交的起始節點。
例如,下面的兩個鏈表:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
在節點 c1 開始相交。
注意:
- 如果兩個鏈表沒有交點,返回
null
. - 在返回結果後,兩個鏈表仍須保持原有的結構。
- 可假定整個鏈表結構中沒有循環。
- 程序盡量滿足 O(n) 時間複雜度,且僅用 O(1) 內存。
思路
對於這道題,也就是我今天想說的重點,這裡給出哈希表,棧,以及雙指針等多種解法!
算法思路直接寫在代碼實現處!
哈希表實現
直接定義一個字典,通過遍歷鏈表A,並將A的所有結點添加到字典當中,循環遍歷鏈表B,在字典中查找鏈表B的當前結點,如果存在,返回即可,否則為空!
def getIntersectionNode(self, headA, headB): dictA={} while headA: dictA[headA]=0 headA=headA.next while headB: if headB in dictA: return headB headB=headB.next return None
棧
這裡定義兩個list用來各自存放對應鏈表的結點,將鏈表A中結點入棧1,結點B中結點入棧2,我們知道只要兩個鏈表相交,那麼從相交點開始到後面的所有結點都一樣!這裡就通過彈出相同的結點,每次彈出的時候保存一下,直到找到兩個鏈表的結點不同為止,此時返回剛才保存的結點,就是第一個相交的結點!
實現步驟:
首先特殊情況處理,然後結點各自入棧!首先需要判斷一下最後結點相同不,如果不相同,直接不相交,返回None即可,否則需要對棧A與B出棧,並判斷元素相同不!
def getIntersectionNode(self, headA, headB): if headA is None or headB is None: return None stackA=[] stackB=[] while headA or headB: if headA: stackA.append(headA) headA=headA.next elif headB: stackB.append(headB) headB=headB.next if stackA[-1]!=stackB[-1]: return None while stackA and stackB: res=stackA[-1] stackA.pop() stackB.pop() # 防止A與B棧空 if stackA and stackB: if stackA[-1].val!=stackB[-1].val: return res else: return res return None
雙指針計算size法
兩個鏈表長度由於不一樣,所以先通過循環找到各自鏈表的長度,然後讓長鏈表的指針先走兩個鏈表長度的差值,保證兩個鏈表遍歷長度一致!此時,讓兩個鏈表去比較,如果此時兩個鏈表有相同結點,則相交,返回其中一個結點即可,否則返回None!
def getIntersectionNode(self, headA, headB): if headA is None or headB is None: return None size_A = 0 size_B = 0 pA = headA pB = headB while pA or pB: if pA: size_A += 1 pA = pA.next elif pB: size_B += 1 pB = pB.next if size_A > size_B: inter = size_A - size_B for i in range(inter): headA = headA.next elif size_A < size_B: inter = size_B - size_A for i in range(inter): headB = headB.next return self.search_Node(headA, headB) def search_Node(self, headA, headB): while headA: if headA.val == headB.val: return headA headA = headA.next headB = headB.next return None
雙指針不計算size法
對於這個實現,網上有個更牛逼的,直接幾行代碼寫完,我們一起來拜讀一下:
def getIntersectionNode(self, headA, headB): p1 = headA p2 = headB while(p1 != p2): p1 = headB if p1 == None else p1.next p2 = headA if p2 == None else p2.next return p1
雙指針判斷有無環狀法
這裡思路是將鏈表A先遍歷到結尾,然後尾部連接頭部,行成一個環,那麼這道題就變成一個鏈表中是否有環問題。然後讓鏈表B的頭結點去訪問即可!這裡通過快慢指針來進行,對於這一塊,之前寫個證明,大家可以翻一下之前文章!
def getIntersectionNode(self, headA, headB): if headA is None or headB is None: return None pA=headA while pA.next: pA=pA.next pA.next=headA return self.detectCycle(headB) def detectCycle(self, head): if not head: return None slow = fast = head while(slow and fast): slow, fast =slow.next, fast.next if fast: fast = fast.next if slow is fast: while(slow is not head): slow, head = slow.next, head.next return head return None
但是可惜這個方法通不過,他不允許修改鏈表結構,哈哈,天真了~~