这篇文章将刷题以来遇到的所有链表类问题做一个总结与回顾：
- 题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
Ying的解法：
这道题要求的是返回一个链表值的列表，而不是节点列表。因此只需要通过遍历链表，将节点值添加到列表中输出即可。
- 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
- 题目描述
输入一个链表，输出该链表中倒数第k个结点。
Ying的解法：
这道题要求返回的是倒数第k个节点，一种做法是：遍历一遍，将链表节点一次存入列表中，然后逆序返回第k个；如果要求空间复杂度为O(1)，则这种方法不可行，下面这种方法是合适的。
还有一种方法是维护两个相距k的指针，相当于滑动窗口，当右边的指针到达链表末尾时，前边的指针正好指向的时倒数第k个节点。
- 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
- 题目描述
输入一个链表，反转链表后，输出新链表的表头。
Ying的解法：
这道题等价于求反转后的链表，有两种思路：一是通过开辟辅助列表空间，一次遍历后将链表节点添加到列表中，逆序列表，然后遍历列表新建一个链表，时间复杂度O(n)，空间复杂度O(n)。二是原地反转，时间复杂度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
- 题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
Ying的解法：
有点归并排序的感觉，时间复杂度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
- 题目描述
输入两个链表，找出它们的第一个公共结点。
Ying的解法：
两个单向链表有公共节点，那么从第一个公共节点之后一直是重合的，即'Y'字型。两个链表可能长度不一样，那么先遍历长的，然后从剩下相同长度开始同时遍历，当遇到第一个值相等的节点时，即为找到的第一个公共节点。
- 链表类问题，头节点往后遍历之前，如果后续还要用到该列表，需要复制一份。
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
- 题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
Ying的解法：
开辟字典辅助空间，由于是单向链表，所以每个节点都是唯一的。在路径中，只有环的入口节点出现两次。
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
- 题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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
- 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
Ying的解法：
新建一个链表对结果进行存储，因为是逆序的，所以链表遍历的顺序就是加法计算的位数顺序。
- 考虑到两个链表长度可能不一样，类似归并排序的做法。
- 同时，最后一个数计算完之后可能有进位，所以作为一种情况考虑。
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
== 待补充==
网友评论