這篇文章將刷題以來遇到的所有鏈表類問題做一個總結(jié)與回顧：
- 題目描述
輸入一個鏈表，按鏈表值從尾到頭的順序返回一個ArrayList。
Ying的解法：
這道題要求的是返回一個鏈表值的列表，而不是節(jié)點列表。因此只需要通過遍歷鏈表，將節(jié)點值添加到列表中輸出即可。
- while True：技巧
- 鏈表的遍歷
def printListFromTailToHead(self, listNode):
# write code here
li = []
while True:
if listNode is None:
break
else:
li.append(listNode.val)
listNode = listNode.next
li.reverse()
return li
- 題目描述
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。
Ying的解法：
這道題要求返回的是倒數(shù)第k個節(jié)點，一種做法是：遍歷一遍，將鏈表節(jié)點一次存入列表中，然后逆序返回第k個；如果要求空間復(fù)雜度為O(1)，則這種方法不可行，下面這種方法是合適的。
還有一種方法是維護兩個相距k的指針，相當(dāng)于滑動窗口，當(dāng)右邊的指針到達鏈表末尾時，前邊的指針正好指向的時倒數(shù)第k個節(jié)點。
- return 和return None都可以
def FindKthToTail(self, head, k):
# write code here
count = 0
node = head
while True:
if head:
count+=1
head = head.next
else:
break
n = count-k+1
if count<k:
return None
i = 1
while True:
if i<n:
node = node.next
i+=1
else:
return node
- 題目描述
輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。
Ying的解法：
這道題等價于求反轉(zhuǎn)后的鏈表，有兩種思路：一是通過開辟輔助列表空間，一次遍歷后將鏈表節(jié)點添加到列表中，逆序列表，然后遍歷列表新建一個鏈表，時間復(fù)雜度O(n)，空間復(fù)雜度O(n)。二是原地反轉(zhuǎn)，時間復(fù)雜度O(n)。
# 方法一：
def ReverseList(self, pHead):
# write code here
li = []
while True:
if pHead is None:
break
else:
li.append(pHead.val)
pHead = pHead.next
li.reverse()
t = len(li)
if t==0:
return None
else:
listNode1 = ListNode(li[0])
listNode3 = listNode1
for i in range(1,t):
listNode2 = ListNode(li[i])
listNode1.next = listNode2
listNode1 = listNode2
return listNode3
# 方法二：
def ReverseList(self, pHead):
# write code here
if not pHead:
return pHead
last = None
while pHead:
tmp = pHead.next
pHead.next = last
last = pHead
pHead = tmp
return last
- 題目描述
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
Ying的解法：
有點歸并排序的感覺，時間復(fù)雜度O(m+n)
def Merge(self, pHead1, pHead2):
# write code here
s = ListNode(0)
pHead3= s
while pHead1 and pHead2:
if pHead1.val<pHead2.val:
pHead3.next = pHead1
pHead1 = pHead1.next
pHead3 = pHead3.next
else:
pHead3.next = pHead2
pHead2 = pHead2.next
pHead3 = pHead3.next
if pHead1:
pHead3.next = pHead1
elif pHead2:
pHead3.next = pHead2
return s.next
- 題目描述
輸入兩個鏈表，找出它們的第一個公共結(jié)點。
Ying的解法：
兩個單向鏈表有公共節(jié)點，那么從第一個公共節(jié)點之后一直是重合的，即'Y'字型。兩個鏈表可能長度不一樣，那么先遍歷長的，然后從剩下相同長度開始同時遍歷，當(dāng)遇到第一個值相等的節(jié)點時，即為找到的第一個公共節(jié)點。
- 鏈表類問題，頭節(jié)點往后遍歷之前，如果后續(xù)還要用到該列表，需要復(fù)制一份。
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
len1 = 0
len2 = 0
ppHead1 = pHead1
ppHead2 = pHead2
while pHead1:
len1+=1
pHead1 = pHead1.next
while pHead2:
len2+=1
pHead2 = pHead2.next
if len1>len2:
k = len1-len2
while k>0:
ppHead1=ppHead1.next
k-=1
else:
k = len2-len1
while k>0:
ppHead2=ppHead2.next
k-=1
while ppHead1 and ppHead2:
if ppHead1.val==ppHead2.val:
return ppHead1
else:
ppHead1 = ppHead1.next
ppHead2 = ppHead2.next
return None
- 題目描述
給一個鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結(jié)點，否則，輸出null。
Ying的解法：
開辟字典輔助空間，由于是單向鏈表，所以每個節(jié)點都是唯一的。在路徑中，只有環(huán)的入口節(jié)點出現(xiàn)兩次。
def EntryNodeOfLoop(self, pHead):
# write code here
dict1 = {}
dict1[pHead] = 1
while pHead.next:
pHead = pHead.next
if pHead not in dict1:
dict1[pHead] = 1
else:
return pHead
return None
- 題目描述
在一個排序的鏈表中，存在重復(fù)的結(jié)點，請刪除該鏈表中重復(fù)的結(jié)點，重復(fù)的結(jié)點不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
def deleteDuplication(self, pHead):
# write code here
if pHead==None or pHead.next==None:
return pHead
p=ListNode(None)
p.next=pHead
pBefore=p
pAfter=pHead.next
while pHead.next!=None:
flag=False
while pAfter!=None and pHead.val==pAfter.val:
if pAfter.next==None:
pBefore.next=None
return p.next
pAfter=pAfter.next
flag=True
if flag:
pBefore.next=pAfter
else:
pBefore=pHead
pHead=pAfter
pAfter=pAfter.next
return p.next
- 兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。
Ying的解法：
新建一個鏈表對結(jié)果進行存儲，因為是逆序的，所以鏈表遍歷的順序就是加法計算的位數(shù)順序。
- 考慮到兩個鏈表長度可能不一樣，類似歸并排序的做法。
- 同時，最后一個數(shù)計算完之后可能有進位，所以作為一種情況考慮。
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
llist = ListNode(0)
result =llist
interval = 0
while l1 and l2:
llist.next = ListNode((l1.val+l2.val+interval)%10)
llist = llist.next
interval = (l1.val+l2.val+interval)//10
l1 = l1.next
l2 = l2.next
while l1:
llist.next = ListNode((l1.val+interval)%10)
llist = llist.next
interval = (l1.val+interval)//10
l1 = l1.next
while l2:
llist.next = ListNode((l2.val+interval)%10)
llist = llist.next
interval = (l2.val+interval)//10
l2 = l2.next
if interval!=0:
llist.next = ListNode(interval)
return result.next
== 待補充==
