...
逻辑上分析「A+B」和「B+A」两条链表，找到公共节点https://singee.atlassian.net/wiki/spaces/MAIN/pages/49316106/Week+41+2024#LC-160.-Intersection-of-Two-Linked-Lists-%E7%9B%B8%E4%BA%A4%E9%93%BE%E8%A1%A8%EF%BC%88%E5%88%A4%E6%96%AD%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4%EF%BC%89
| Code Block |
|---|
|
/**
* 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/
| Code Block |
|---|
/**
* 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
| Code Block |
|---|
|
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
slow, fast := head, head
for fast != nil {
for fast != nil && slow.Val == fast.Val {
fast = fast.Next
}
slow.Next = fast
slow = slow.Next
}
return head
} |
快慢指针 II
注意：该解法使用了 LC 26 的思路 —— 不停维护 slow 对应的链表的长度作为返回的链表
| Code Block |
|---|
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
slow, fast := head, head
for fast != nil {
if fast.Val != slow.Val {
// nums[slow] = nums[fast];
slow.Next = fast
// slow++;
slow = slow.Next
}
// fast++
fast = fast.Next
}
// 断开与后面重复元素的连接
slow.Next = nil
return head
} |
LC 82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
| Code Block |
|---|
|
/**
* 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 {
initialP := p
for p.Next != nil && p.Val == p.Next.Val {
p = p.Next
}
if initialP == p {
// not jump
prev = p
p = p.Next
} else {
// jump all p
prev.Next = p.Next
p = p.Next
}
}
return dummy.Next
} |
LC 264. Ugly Number II 丑数 II
https://leetcode.com/problems/ugly-number-ii/
| Code Block |
|---|
|
func nthUglyNumber(n int) int {
p2, p3, p5 := 1, 1, 1
h2, h3, h5 := 1, 1, 1
ugly := make([]int, n+1)
for i := 1; i <= n; i++ {
h := min(h2, h3, h5)
ugly[i] = h
if h == h2 {
h2 = 2 * ugly[p2]
p2++
}
if h == h3 {
h3 = 3 * ugly[p3]
p3++
}
if h == h5 {
h5 = 5 * ugly[p5]
p5++
}
}
return ugly[n]
} |
LC 263. Ugly Number 丑数
https://leetcode.com/problems/ugly-number/description/
| Code Block |
|---|
|
func isUgly(n int) bool {
for n >= 2 && n % 2 == 0 {
n /= 2
}
for n >= 3 && n % 3 == 0 {
n /= 3
}
for n >= 5 && n % 5 == 0 {
n /= 5
}
return n == 1
} |