双指针

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意：**此题对比原题有改动

**示例 1:**

<pre>**输入:** head = [4,5,1,9], val = 5
**输出:** [4,1,9]
**解释:** 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
</pre>

**示例 2:**

<pre>**输入:** head = [4,5,1,9], val = 1
**输出:** [4,5,9]
**解释:** 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
</pre>

//指针
func deleteNode(head *ListNode, val int) *ListNode {
    if head.Val == val {
        return head.Next
    }

    pre := head
    for pre.Next != nil && pre.Next.Val != val {
        pre = pre.Next
    }

    if pre.Next != nil {
        pre.Next = pre.Next.Next
    }
    return pre
}

//递归
func deleteNode(head *ListNode, val int) *ListNode {
    if head.Val == val {
        return head.Next
    }

    head.Next = deleteNode(head.Next, val)
    return head
}

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast, slow := head, head
    for fast != nil && k > 0 {
        fast = fast.Next
        k--
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }

    if l2 == nil {
        return l1
    }

    if l1.Val > l2.Val {
        l1, l2 = l2, l1
    }

    l1.Next = mergeTwoLists(l1.Next, l2)
    return l1
}

剑指 Offer 52. 两个链表的第一个公共节点

// map
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var newMap = map[*ListNode]bool{}

    for tmp := headA; tmp != nil; tmp = tmp.Next {
        newMap[tmp] = true
    }

    for tmp := headB; tmp != nil; tmp = tmp.Next {
        if newMap[tmp] {
            return tmp
        }
    }
    return nil
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headB == nil || headA == nil {
        return nil
    }

    pa, pb := headA, headB
    for pa != pb {
        if pa == nil {
            pa = headB
        } else {
            pa = pa.Next
        }

        if pb == nil {
            pb = headA
        } else {
            pb = pb.Next
        }
    }
    return pa
}

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

#### [](https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

**示例：**

<pre>**输入：**nums = [1,2,3,4]
**输出：**[1,3,2,4] 
**注：**[3,1,2,4] 也是正确的答案之一。</pre>

**提示：**

1.  `0 <= nums.length <= 50000`
2.  `0 <= nums[i] <= 10000`

func exchange(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    left, right := 0, n-1

    for _, num := range nums {
        if num%2 == 1 {
            ans[left] = num
            left++
        } else {
            ans[right] = num
            right--
        }
    }
    return ans
}

剑指 Offer 57. 和为s的两个数字

func twoSum(nums []int, target int) []int {
    left, right := 0, len(nums)-1

    for left < right {
        if nums[left] + nums[right] == target {
            return []int{nums[left], nums[right]}
        } else if nums[left] + nums[right] > target {
            right--
        } else {
            left++
        }
    }
    return []int{}
}