Week 52 @ 2024 算法周记【双指针链表 + 双指针数组】
- Bryan
Owned by Bryan
双指针链表
LC 234. Palindrome Linked List 回文链表
Palindrome Linked List - LeetCode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
mid := getMid(head)
prev, h := mid, mid.Next
for h != nil {
next := h.Next
h.Next = prev
prev = h
h = next
}
mid.Next = nil
l, r := head, prev
// printList(l)
// printList(r)
for l != r && l != nil && r != nil {
// fmt.Println("compare", l.Val, r.Val)
if l.Val != r.Val {
return false
}
l = l.Next
r = r.Next
}
return true
}
// func printList(head *ListNode) {
// for head != nil {
// fmt.Print(head.Val, " -> ")
// head = head.Next
// }
// fmt.Println("END")
// }
func getMid(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}整理下代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
mid := getMid(head)
l, r := head, reverse(mid)
for l != nil && r != nil {
if l.Val != r.Val {
return false
}
l = l.Next
r = r.Next
}
return true
}
func getMid(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}双指针数组
LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项
Remove Duplicates from Sorted Array - LeetCode
判断当前元素是否重复
func removeDuplicates(nums []int) int {
slow, fast := 1, 1
for fast < len(nums) {
if nums[fast] == nums[fast-1] {
fast++
continue
}
nums[slow] = nums[fast]
slow++
fast++
}
return slow
}判断当前元素是否已存在
LC 27. Remove Element 移除元素
LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
Two Sum II - Input Array Is Sorted - LeetCode
LC 344. Reverse String 反转字符串
LC 5. Longest Palindromic Substring 最长回文子串
Longest Palindromic Substring - LeetCode
LC 80 删除有序数组中的重复项 II
Remove Duplicates from Sorted Array II - LeetCode
待复习