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
}
交替行走法
待复习
/**
* 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
/**
* 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 对应的链表的长度作为返回的链表
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/
/**
* 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/
待复习
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/
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
}