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

By Bryan
3 min

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

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

 

Related content