Week 49 @ 2024 算法周记【双指针链表】

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」两条链表，找到公共节点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

/**
 * 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
}