多種解法破解鏈表

  • 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  

但是可惜這個方法通不過,他不允許修改鏈表結構,哈哈,天真了~~