Week 49 @ 2024 算法周记【双指针链表】
- Bryan
Owned by Bryan
LC 160. Intersection of Two Linked Lists 相交链表
https://leetcode.com/problems/intersection-of-two-linked-lists/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
lA := getLength(headA)
lB := getLength(headB)
if lB < lA {
headA, headB = headB, headA
lA, lB = lB, lA
}
for i := 0; i < lB-lA; i++ {
headB = headB.Next
}
for headA != headB {
headA = headA.Next
headB = headB.Next
}
return headA
}
func getLength(head *ListNode) int {
l := 0
for head != nil {
l++
head = head.Next
}
return l
}交替行走法
待复习
逻辑上分析「A+B」和「B+A」两条链表，找到公共节点Week 41 @ 2024 算法周记【双指针链表】 | LC 160. Intersection of Two Linked Lists 相交链表（判断两个链表是否相交）
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
p1 := headA
p2 := headB
for p1 != p2 {
if p1 == nil {
p1 = headB
} else {
p1 = p1.Next
}
if p2 == nil {
p2 = headA
} else {
p2 = p2.Next
}
}
return p1
}LC 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Val: -1024, Next: head}
prev, p := dummy, head
for p != nil {
if p.Val == prev.Val {
prev.Next = p.Next
p = p.Next
} else {
prev = p
p = p.Next
}
}
return dummy.Next
}快慢指针 I
快慢指针 II
注意：该解法使用了 LC 26 的思路 —— 不停维护 slow 对应的链表的长度作为返回的链表
LC 82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
LC 264. Ugly Number II 丑数 II
https://leetcode.com/problems/ugly-number-ii/
待复习
LC 263. Ugly Number 丑数