1.数据结构-链表问题
2020-10-04 本文已影响0人
做一只有趣的芦苇
链表相关问题
- 删除节点
- 链表去重
- 有环链表
- 反转链表
- 链表排序
- 链表相交
- 其他问题
面试题 02.03. 删除中间节点
- 把b的值换成c的值 b.val = c.val
- 让b的后面节点变成b的后面的后面 b.next = b.next.next
删除链表倒数第n个节点
之前太轻视这个问题了，百度面试的时候也没有一次性写出 bug free的代码，再好好过一下 。要注意虽然双指针是很容易想到的一个思路，但是要确保写出bug free的代码
def removeNthFromEnd(self , head , n ):
# write code here
p1 = p2 = head # 这个写法是没有问题的
for _ in range(n): # 用for比while 要简洁得多，第一时间为什么想的是while
p1 = p1.next
# 这里是最关键的一个部分，
# 题目虽然说保证n是有效的，但是当倒数第N个元素是头结点的时候，
# 那也是有效的，这是一个特殊情况，这时要返回 head.next
if not p1:
return head.next
while(p1.next):
p1 = p1.next
p2 = p2.next
# 这里也要注意，p2.next.next可能不存在
if p2.next.next:
p2.next = p2.next.next
else:
p2.next = None
return head
这里有个类似的问题，不是删除是返回倒数第K个节点
面试题 02.02. 返回倒数第 k 个节点
- 双指针
def kthToLast(self, head: ListNode, k: int) -> int:
a=head
b=head
for i in range(k):
b=b.next
while b:
a=a.next
b=b.next
return a.val
- 进行一次遍历放到数组中
def kthToLast(self, head: ListNode, k: int) -> int:
arr = []
while(head):
arr.append(head.val)
head = head.next
return arr[-k]
删除链表中重复的元素
初始思路:用两个while循环，内层while循环是一直循环到和前面的元素不相等的元素，效率较低
第二个是双指针法, 要画画草图
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head: return []
p1 = head.next
p2 = head
while p1:
if p1.val == p2.val:
p1 = p1.next
if not p1:
p2.next = None
else:
p2.next = p1
p2 = p1
p1 = p1.next
return head
判断链表是否有环
- 双指针法
- 让后面的节点的next都指向head, 然后当next==head时，说明环已经出现
def hasCycle(self, head: ListNode) -> bool:
if not head: return False
# method 1 双指针法
# slow = fast = head
# while(fast and fast.next): #注意这里要判断 fast and fast.next
# fast = fast.next.next
# slow = slow.next
# if(slow == fast):
# return True
# return False
# method 2
p = head.next
while(p):
nex = p.next
if(nex == head):
return True
else:
p.next = head
p = nex
return False
衍生题目->返回环的入口位置 力扣142题
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast == slow: break
else: return # 注意这里要加else 因为比如只有一个节点的情况 fast没有next,要直接返回的
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
反转链表
- 反转单链表
def reverserLink(head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
- K个一组反转-字节
def reverseKGroup(self , head , k ):
# 基本功：反转一个单链表， 这里唯一的区别是知道了tail
def helper(head, tail):
pre = tail.next #区别
cur = head
while pre!=tail: #头指针迭代到末尾：
tem = cur.next
cur.next = pre
pre = cur
cur = tem
return tail, head
hair = ListNode(0)
hair.next = head
pre = hair
while head:
tail = pre
for _ in range(k):
tail = tail.next
if not tail:
return hair.next
tem = tail.next
head, tail = helper(head, tail)
#连接回去
pre.next = head
tail.next = tem
#更新状态量
pre = tail
head = tail.next
return hair.next
链表排序
对于链表我们可以递归地将当前链表分为两段，然后merge，分两段的方法是使用双指针法，p1指针每次走两步，p2指针每次走一步，直到p1走到末尾，这时p2所在位置就是中间位置，这样就分成了两段。
def sortList(self, head: ListNode) -> ListNode:
if not head: return head
return self.mergeSort(head)
def mergeSort(self, node: ListNode) -> ListNode:
if not node.next: return node #递归结束的标准：node后面没有节点了，直接返回node
p1 = p2 = node
cute = None
while(p1 and p1.next):
cute = p2 # 因为循环结束时 p2已经跑到后面一条链去了 所以要记录p2之前的node
p2 = p2.next
p1 = p1.next.next
cute.next = None # 分开的前半条链最后一个Node的next是空
l1 = self.mergeSort(node)
l2 = self.mergeSort(p2)
return self.mergeTwoLists(l1,l2)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
tmp = dummy
while(l1 and l2):
if(l1.val<l2.val):
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l1: #注意对于链表 直接if 不需要while
tmp.next = l1
#l1 = l1.next 注意对于链表直接接上去就ok l1无需继续往后走
if l2:
tmp.next = l2
# l2 = l2.next
return dummy.next
143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
def reorderList(self, head: ListNode) -> None:
if not head: return None
vec=[]
p = head
while(p):
vec.append(p)
p=p.next
i,j=0,len(vec)-1
while(i<j):#这一段有点意思 注意顺序
vec[i].next=vec[j]
i+=1#先加1为了vec[j]有next
if(i==j): #如果相等就中止，是中间点
break
vec[j].next=vec[i]
j-=1
vec[i].next=None #最后记得中间点next是None
链表相交 160题 字节
考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pB 比 pA 少经过 2 个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。
如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pa,pb = headA,headB
while(pa != pb):
pa = pa.next if pa else headB
pb = pb.next if pb else headA
return pa
其他链表题目
2. 两数相加
我觉得自己的思路是没有问题的，虽然代码看上去冗余了一些，但是节省了内存空间，当然在有进位的情况下会对原来的链表造成修改
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
pre = hair = ListNode()
while(l1 and l2):
pre.next = ListNode((l1.val + l2.val + carry)%10)
carry = (l1.val + l2.val + carry)//10
pre = pre.next
l1,l2 = l1.next,l2.next
if l1:
pre.next = l1
while(carry==1):
s, carry = (l1.val + carry)%10,(l1.val + carry)//10
l1.val = s
if l1.next: l1 = l1.next
elif carry == 1:
l1.next = ListNode(1,None)
break #这里注意写程序的基本sense 什么时候跳出循环，有时只靠while后面跟的条件是不够的，判断新加了一个节点之后就可以结束了
elif l2:
pre.next = l2
while(carry==1):
s,carry = (l2.val + carry)%10, (l2.val + carry)//10
l2.val = s
if l2.next: l2 = l2.next
elif carry == 1:
l2.next = ListNode(1,None)
break
elif carry == 1:
pre.next = ListNode(1,None)
return hair.next
23. 合并K个升序链表
# 假设一共有k个链表 平均长度为n 一共有nk个元素
# 每次从k个链表头中选最小，考虑用堆
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
hair = ListNode(0)
p = hair
heads = []
# 用所有链表头初始化堆 时间复杂度 O(k)
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heads, (lists[i].val, i))
lists[i] = lists[i].next
# print(heads)
while heads: # 每次用大小为k的最小堆 过滤nk个元素 时间复杂度 O(nk*log(k))
val, idx = heapq.heappop(heads) # 弹出堆中最小值 时间复杂度为 O(log(k))
p.next = ListNode(val)
p = p.next
if lists[idx]: # 将弹出节点的后续节点依次入堆
heapq.heappush(heads, (lists[idx].val, idx))
lists[idx] = lists[idx].next
return hair.next
147. 对链表进行插入排序
def insertionSortList(self, head: ListNode) -> ListNode:
if not head : return None # 判空
dummy = ListNode(0) # 创建dummy节点
dummy.next = head
pivot = head # 已经完成排序的最后一个节点
cur = head.next # 待插入节点
while cur:
if pivot.val <= cur.val: # 已经满足升序 pivot和cur均向后移动一步
pivot = pivot.next
else: # 从头遍历 寻找插入位置 注意连接指针的先后顺序
pre = dummy
while pre.next.val <= cur.val:
pre = pre.next
pivot.next = cur.next
cur.next = pre.next
pre.next = cur
cur = pivot.next # 移动到下一个位置
return dummy.next
