使用双指针解决数组问题

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

题目描述

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

示例

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
 

解题思路

一、双指针，取余

1. 使用双指针分别指向数组首位元素下标；

2. 当左下标小于右下标，且当前左下标对应元素为奇数，左指针就一直往后移动，直达指向偶数；

3. 当左下标小于右下标，且当前右下标对应元素为偶数，右指针就一直往前移动，直到指向奇数；

4. 当左指针指向偶数，右指针指向奇数时，两个元素交换位置；

5. left = right时，遍历结束，返回数组即为所求结果。

代码实现：

func exchange(nums []int) []int {
    left, right := 0, len(nums) - 1
    for left < right {
        for (left < right) && (nums[left] % 2 == 1) {   // 左边指针遇到奇数一直后移，直到遇到偶数
            left++
        }
        for (left < right) && (nums[right] % 2 == 0) {  // 右边指针遇到偶数一直前移，直到遇到奇数
            right--
        }
        nums[left], nums[right] = nums[right], nums[left] // 直到指针指向偶数，右指针指向奇数，此时交换
    }
    return nums
}

运行效果：

二、双指针，按位与

代码实现：

func exchange(nums []int) []int {
    left, right := 0, len(nums) - 1
    for left < right {                  // 左下标小于由下表就一直循环，直到相等结束循环
        if(nums[left] & 1 == 1) {       // 左下标对应元素为奇数，任何奇数与1按位与结果为1
            left++                      // 左指针向后移动
            continue                    // 跳过后面的程序，进入下一轮循环
        }
        if(nums[right] & 1 == 0) {      // 由下标对应元素为偶数，任何偶数与1按位与结果为0
            right--                     // 右指针向前移动
            continue                    // 跳过后面的程序，进入下一轮循环
        }
        nums[left], nums[right] = nums[right], nums[left]  // 直到左右指针分别指向奇数和偶数，交换
    }

    return nums
}

运行效果：

使用双指针解决链表问题

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

问题描述

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

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

示例

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

返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
 

解题思路

一、左右双指针：

1. 声明left，right两个指针为ListNode的指针类型（这样不用判断k是否大于链表长度，直接返回遍历结束时left指向的链表即为结果）；

2. 当前指针先指向链表首节点，然后这个遍历链表；

3. 使用num统计当前遍历的节点个数，如果等于k，则左指针指向链表首节点，右指针指向当前正在遍历的节点；

4. 当走过的节点数num大于k时，左右指针一起往后遍历，直达链表遍历结束；

5. 链表遍历结束，不管链表长度是否大于k，直接返回left指向的节点即可（因为，如果链表长度小于k，left指向空节点；大于等于k则不为空）。

实现代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func getKthFromEnd(head *ListNode, k int) *ListNode {
    var left, right *ListNode  // 前后双指针
    cur := head                // cur表示当前节点，先指向首节点
    var num int                // 统计走过的节点个数
    for cur != nil {           // 链表逐节点遍历
        num++                  // 统计当前遍历的节点数
        cur = cur.Next         // 统计完节点数，当前头节点指向下一个节点
        if num == k {          // 如果遍历的节点数等于k，则左右指针分别指向链表首节点和当前节点
            left = head        // 左指针指向首节点
            right = cur        // 右指针指向当前节点
            
        } else if num > k {    // 然后，左右指针一起往后移动，直到当前节点指向链表尾部nil节点
            left = left.Next
            right = right.Next
        }
    }

    return left                 // 遍历结束，返回左指针即为所求
}

运行结果：

二、快慢指针

主要思路：

1. 当快指针 fast 走了k步的时候慢指针slow 开始走 

2.当慢指针 slow 走出的时候（即超出边界）此时的 slow 位置即为链表中倒数第k个节点 

代码实现：

func getKthFromEnd(head *ListNode, k int) *ListNode {
    slow, fast, cur := head, head, head  // 快慢、当前指针分别指向头节点
    for cur != nil {                     // 当前指针沿着链表逐节点遍历
        fast = fast.Next                 // 快指针先走k步
        if k > 0 {                       // 统计什么时候走过k个节点
            k--
        } else {                         // 当走过k个节点后，慢指针才跟快指针一起往后遍历
            slow = slow.Next
        }
        cur = cur.Next                   // 当前节点后移
    }

    return slow                          // 返回慢指针
}

运行效果：

61. 旋转链表

问题描述

难度中等504收藏分享切换为英文接收动态反馈

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例说明

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

思路分析

1. 定义慢指针slow和快指针fast，其初始都指向链表头节点。

2. 让快指针fast先向前移动k步。

3. 慢指针slow和快指针fast同时向前移动，每次移动一步，直到快指针fast指向链表的尾节点。这里，快指针fast指向链表的尾节点，不再继续向后移动的原因是，需要将尾节点和链表头节点相连，因此其所指节点不能为null。此时，慢指针slow所指节点的下一个节点就是倒数第K个节点。

4. 将快指针fast所指的尾节点的后继指针指向链表头节点，使链表成环。

5. 倒数第K个节点作为链表旋转后的新的头节点，指针slow所指节点作为新的尾节点。

代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil {            // 链表为空，count=0，直接返回
        return nil 
    }
    var count int 
    cur := head 
    for cur != nil {            // 计算链表长度
        count++
        cur = cur.Next
    }

    k = k % count               // 当做环形链表的循环移动，当k超过链表长度时，人为移动k与k%count个节点效果一样
    slow, fast := head, head    // 快慢指针，初始时都指向头结点
    for i := 0; i < k; i++ {    // 快指针先移动k个节点
        fast = fast.Next    
    }
    for fast.Next != nil {      // 快指针移动k个节点后，快慢指针一起向后移动，直到快指针移动到最后一个节点，此时fast.Next = nil
        fast = fast.Next
        slow = slow.Next
    }

    fast.Next = head            // 链表的尾节点指向原来的头结点
    cur = slow.Next             // slow节点的Next为旋转后新链表的头结点
    slow.Next = nil             // slow节点为新链表的尾节点，断开之后的连接

    return cur 
}

最后

以上就是舒服仙人掌为你收集整理的双指针解决数组链表问题使用双指针解决数组问题使用双指针解决链表问题的全部内容，希望文章能够帮你解决双指针解决数组链表问题使用双指针解决数组问题使用双指针解决链表问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。