当前位置:网站首页>Interview essential leetcode linked list algorithm question summary, whole process dry goods!
Interview essential leetcode linked list algorithm question summary, whole process dry goods!
2022-07-04 22:21:00 【Wu_ Candy】
introduction :
The difficulty of collecting questions is at the simple level and intermediate level , It is also a common topic in interviews . Problem solving , The development language used is Swift.
Because the description of the topic is very long , And there are various case tips , In order not to occupy space , So it didn't show , You can check the description of the topic directly through the question number query .
The writing order of the article is :
1. Show the title number and the link to the title
2. The core idea
3. Code implementation .
Finally, the code provided in this article is in LeetCode Mention the traffic .
1. Linked List Questions( Linked list related problems )
1.LeetCode_141: Is there a link in the list 2.LeetCode_160: Intersecting list 3.LeetCode_206: List reversal 4.LeetCode_ 21: Merge two ordered lists 5. The finger of the sword offer_ 22: Last in the list k Nodes 6. The finger of the sword Offer_ 06: Print linked list from end to end 7.LeetCode_ 19: Delete the last of the linked list N Nodes 8.LeetCode_237: Delete the nodes in the list 9.LeetCode_ 83: Delete duplicate elements from the sort list 10.LeetCode_ 82: Delete all duplicate elements in the sorting linked list II 11.LeetCode_203: Delete all nodes of a value in the linked list 12.LeetCode_ 86: Separate the list 13.LeetCode_328: Odd and even list
1. Is there a link in the list
1.1 Explain the core idea
This idea uses the speed pointer . analogy : Like the school playground ,A、B They ran around the playground ,A Slow running ,B Run fast , After they started running , as time goes on , Eventually they will meet somewhere on the playground . If A、B Running on a highway , One slow, one fast , They never had a chance to meet . The speed pointer uses the above principle ,
slow
The pointer goes one step at a time ,quick
The pointer takes two steps at a time . Traverse the entire linked list in this way . If you don't meet, there is no ring , It's like a highway . If we meet each other , Description ring , Like the circular track on the school playground .
1.2 Code implementation
func hasCycle(_ head: ListNode?) -> Bool {
if head == nil || head?.next == nil { return false }
var slow = head
var fast = head?.next
while fast != nil && fast?.next != nil {
if slow === fast { return true }
slow = slow?.next
fast = fast?.next?.next
}
return false
}
2. The list intersects
2.1 Explain the core idea
You become me , I become you , We met . Then why can we meet ? Set long linked list A The length is LA, Short list length LB; Because of the same speed , Then in the long linked list A Walk the LA Length , Short linked list B Have turned their heads in A Let's go LA-LB The length of , The remaining length to go is LA-(LA-LB) = LB; Then long linked list A Turn your head around B Go up , The remaining length to go is also LB; That is to say, there are currently two linked lists “ alignment ” 了 . therefore , The next same node is the intersection of the two linked lists . What if there is no intersection between the two linked lists ? answer : In that case, No 4 Step will be executed until the end of the two linked lists ,la,lb All for null, It's going to jump out of the loop , return null.
2.2 Code implementation
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var currentA = headA
var currentB = headB
// !== Using the opposite image is not equal to No !=
while currentA !== currentB {
currentA = (currentA != nil) ? currentA?.next : headB
currentB = (currentB != nil) ? currentB?.next : headA
}
return currentA
}
3. List reversal
3.1 Explanation of problem-solving methods
Set up three nodes pre
、cur
、next
(1) Every time you check cur
Whether the node is NULL
, If it is , End cycle , Get the results (2) If cur
The node is not NULL
, Then set the temporary variable first next
by cur
The next node of (3) Give Way cur
The next node of becomes a point pre
, Then pre
Move cur
,cur
Move to next
(4) repeat (1)(2)(3) (5) return pre
)
3.2 Code implementation
func reverseList(_ head: ListNode?) -> ListNode? {
var pre: ListNode?
var cur = head
var next = head?.next
while cur != nil {
next = cur?.next
cur?.next = pre // reverse , Point to pre
pre = cur
cur = next
}
return pre
}
4. Merge two ordered lists
4.1 The core idea of algorithm
Because it's hard to judge at first l1 and l2 Who is the empty node , So create dummy This empty node ; Through the nodes of two linked lists val Size contrast , Update empty list pointer cur value Each update cur After value , Update the pointers of two ordered linked lists at the same time , Save linked list pointer cur To the latest location Last return To dummy.next, That is, the head node can get the whole linked list
4.2 Code implementation
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
if l1 == nil { return l2 }
if l2 == nil { return l1 }
// Create an empty node , And let cur The pointer points to it , It provides convenience for the final return result , It's a good skill
var dummy = ListNode()
var cur: ListNode? = dummy
var headA = l1
var headB = l2
while headA != nil && headB != nil {
if headA!.val < headB!.val {
cur?.next = headA
headA = headA?.next
} else {
cur?.next = headB
headB = headB?.next
}
cur = cur?.next
}
if headA == nil {
cur?.next = headB
}
if headB == nil {
cur?.next = headA
}
return dummy.next
}
5. Last in the list k Nodes
5.1 The core idea
Double pointer l r r Pointer first k-1 Step , such l Pointers and r The difference between the pointers k-1. This is the time l and r Go back together , When r Go to the end of the list ,l The pointer is just the penultimate k Nodes
5.2 Code implementation
func getKthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
if head == nil || k == 0 { return head }
var count = k
var l: ListNode? = head
var r: ListNode? = head
while count > 1 {
guard let node = r?.next else { return nil }
count -= 1
r = node
}
while r?.next != nil {
l = l?.next
r = r?.next
}
return l
}
6. Print the linked list in reverse order
6.1 The core idea
Since the reverse order , Then use recursion
6.2 Code implementation
var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
if head == nil { return nums }
reverse(head)
nums.append(head!.val)
return nums
}
func reverse(_ head: ListNode?) {
guard let next = head?.next else { return }
reverse(head?.next)
nums.append(next.val)
}
Or so :
var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
guard let head = head else {
return []
}
reversePrint(head.next)
nums.append(head.val)
return nums
}
7. Delete the last of the linked list N Nodes
7.1 The core idea
This topic is similar to 5 The idea of the question is the same . But there is a very special case : Suppose the length of the linked list is N, Delete the last N The first node is the head node . In order to deal with this special situation , We can start from 4 Get inspiration from the question , Is to create a virtual empty node dummy, And let dummy.next = head that will do .
7.2 Code implementation
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
if head == nil || n == 0 { return nil }
var count = n
var dummy = ListNode(0,head)
var first: ListNode? = dummy
var second: ListNode? = dummy
while count > 0 {
guard let node = second?.next else { return nil }
second = node
count -= 1
}
while second?.next != nil {
second = second?.next
first = first?.next
}
first?.next = first?.next?.next
return dummy.next
}
8. Delete the nodes in the list
8.1 The core idea
Thought analysis If we want to delete a node in the list , The general operation is : Modify the pointer of the previous node of the node to be deleted Point the pointer to the next node that you want to delete for example , Linked list
[4, 5, 1, 9]
in , When we want to delete nodes5
when , We will modify the nodes5
Last node4
The pointer to , Let it point to the node5
The next node of , That is node1
. But this problem only tells us the nodes to be deleted , We don't know what the previous node of this node is , What should I do at this time ? Since we need to know the last node when we want to delete a node , If we don't know the last node , Let's find a node that can know the previous node , Make it the node to delete , Then delete it . It sounds like a bit of a mouthful ? Don't worry , Let's look at an example ! still [4, 5, 1, 9] Linked list , Or delete the node 5. First , We put the nodes 5 The value of the next node is assigned to it , The node becomes[4, 1, 1, 9]
Then delete the third node 1 that will do
8.2 Code implementation
func deleteNode(_ node: ListNode?) {
guard let node = node else { return }
var nextNode = node.next
node.val = nextNode!.val
node.next = nextNode!.next
}
9. Delete duplicate elements from the sort list
9.1 The core idea
Appoint cur The pointer points to the head head When cur and cur.next The existence of is the end of the loop condition , When one of the two does not exist, it means that there is no need to repeat the linked list When cur.val and cur.next.val When equal, it means that the weight needs to be removed , Will cur The next pointer of points to the next , In this way, we can achieve the effect of de repetition If not, then cur Move to the next position and continue the cycle
Solution 2 :
There's another solution : Inspiration comes from 2 The arithmetic problem of the sum of numbers , Use map The thought of weight removal .
9.2 Code implementation
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var cur = head
while cur != nil && cur?.next != nil {
if cur!.val == cur!.next!.val {
cur?.next = cur?.next?.next
} else {
cur = cur?.next
}
}
return head
}
func removeDuplicateNodes(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var map:[Int: ListNode] = [:]
var p = head
map[p!.val] = p!
while p?.next != nil {
if map[p!.next!.val] != nil {
p!.next = p!.next!.next
} else {
map[p!.next!.val] = p!.next!
p = p?.next
}
}
return head
}
10. Delete all duplicate elements in the sorting linked list II
10.1 The core idea
Because the given linked list is in good order , Therefore, the position of repeated elements in the linked list is continuous , Therefore, we only need to traverse the linked list once , You can delete duplicate elements . Because the head node of the linked list may be deleted , So we need to use an extra dummy node (dummy node) Point to the head node of the list . In particular , We start with the pointer cur Point to the dummy node of the linked list , Then start traversing the linked list . If at present cur.next And cur.next.next The corresponding elements are the same , So we're going to have to cur.next And all linked list nodes with the same element value are deleted . Let's write down the value of this element x, Then continue to cur.next Remove from list , until cur.next Null node or its element value is not equal to x until . here , We set the values of all elements in the linked list to x Delete all nodes . If at present cur.next And cur.next.next The corresponding elements are different , Then it means that only one element in the linked list has a value of cur.next The node of , So we can put cur Point to cur.next. After traversing the entire linked list , We return the next node of the dummy node of the linked list dummy.next that will do .
10.2 Code implementation
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var dummy = ListNode(0,head)
var cur: ListNode? = dummy
while cur?.next != nil && cur?.next?.next != nil {
if cur!.next!.val == cur!.next!.next!.val {
let x = cur!.next!.val
// secondary while Delete duplicate nodes
while cur?.next != nil && cur!.next!.val == x {
cur?.next = cur?.next?.next
}
} else {
cur = cur?.next
}
}
return dummy.next
}
11. Delete all nodes of a value in the linked list
11.1 The core idea
Because the worry node is also a deleted node , So add one at the beginning dummy Virtual node . The next step is to delete . especially
cur?.next = cur?.next?.next // Execution deletion
this sentence , Just keep deleting , Until the next node value is not equal to val, Just letcur = cur?.next
11.2 Code implementation
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
if head == nil { return head }
var dummy = ListNode(0, head)
var cur: ListNode? = dummy
while cur?.next != nil {
if cur!.next!.val == val {
cur?.next = cur?.next?.next // Execution deletion
}else {
cur = cur?.next
}
}
return dummy.next
}
12. Split the list
12.1 The core idea
2 Create a new linked list to save , Finally, put two more 2 Just link the linked list
12.2 Code implementation
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
if head == nil { return nil }
var node = head
var lHead = ListNode(0), lTrail = lHead
var rHead = ListNode(0), rTrail = rHead
while node != nil {
if node!.val < x {
lTrail.next = node
lTrail = lTrail.next! //lTrail = curHead!
}else {
rTrail.next = node
rTrail = rTrail.next! // rTrail = curHead!
}
node = node?.next
}
rTrail.next = nil
lTrail.next = rHead.next
return lHead.next
}
13. Odd and even list
13.1 The core idea
and 12 The solution of the problem is the same , Just change the judgment conditions
13.2 Code implementation
func oddEvenList(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var node = head
var lHead = ListNode(0), lTrail = lHead
var rHead = ListNode(0), rTrail = rHead
var flag = false
while node != nil {
if !flag {
lTrail.next = node
lTrail = lTrail.next!
}else {
rTrail.next = node
rTrail = rTrail.next! // rTrail = curHead!
}
flag.toggle()
node = node?.next
}
rTrail.next = nil
lTrail.next = rHead.next
return lHead.next
}
end
边栏推荐
- B站大量虚拟主播被集体强制退款:收入蒸发,还倒欠B站;乔布斯被追授美国总统自由勋章;Grafana 9 发布|极客头条
- WebGIS框架---kalrry
- 力扣_回文数
- 删库不必跑路!详解 MySQL 数据恢复
- Challenges faced by virtual human industry
- Interview question 01.01 Determine whether the character is unique
- [acwing] solution of the 58th weekly match
- Use blocconsumer to build responsive components and monitor status at the same time
- Nat. Commun.| 机器学习对可突变的治疗性抗体的亲和力和特异性进行共同优化
- 什么是商业智能(BI),就看这篇文章足够了
猜你喜欢
Introduction and application of bigfilter global transaction anti duplication component
Redis sentinel simply looks at the trade-offs between distributed high availability and consistency
HUAWEI nova 10系列发布 华为应用市场筑牢应用安全防火墙
Kdd2022 | what features are effective for interaction?
Concurrent optimization summary
El tree combined with El table, tree adding and modifying operations
From repvgg to mobileone, including mobileone code
常用的开源无代码测试工具
机器学习笔记 - 互信息Mutual Information
A large number of virtual anchors in station B were collectively forced to refund: revenue evaporated, but they still owe station B; Jobs was posthumously awarded the U.S. presidential medal of freedo
随机推荐
Force buckle_ Palindrome number
机器学习笔记 - 互信息Mutual Information
Éducation à la transmission du savoir | Comment passer à un test logiciel pour l'un des postes les mieux rémunérés sur Internet? (joindre la Feuille de route pour l'apprentissage des tests logiciels)
ACM multimedia 2022 | counterfactual measurement and elimination of social prejudice in visual language pre training model
Tiktok actual combat ~ the number of comments is updated synchronously
283. 移动零-c与语言辅助数组法
Common shortcut keys for hbuilder x
Locust性能测试 —— 环境搭建及使用
HDU - 1078 FatMouse and Cheese(记忆化搜索DP)
能源势动:电力行业的碳中和该如何实现?
PostgreSQLSQL高级技巧透视表
面试题 01.08. 零矩阵
php短视频源码,点赞时会有大拇指动画飘起
Why do you have to be familiar with industry and enterprise business when doing Bi development?
置信区间的画法
Bookmark
odps 中 对表进行了一次备份,为什么在元数据库查m_table 时,两张表的逻辑大小不一致,但数
HUAWEI nova 10系列发布 华为应用市场筑牢应用安全防火墙
网上开户哪家证券公司佣金最低,我要开户,网上开户安全吗
删库不必跑路!详解 MySQL 数据恢复